TAKEAWAY 7.16 재귀호출이 많으면 계산 시간이 지수적으로 증가할 수 있다.
그림 7-3에 나온 중첩 호출 과정을 보면 fib(2)가 두 번 호출되는 것을 볼 수 있다. 즉, fib(2)의 계산 과정이 중복되어 시간 낭비를 한 셈이다. 다음에 나오는 fibCacheRec 함수는 이런 중복을 제거했다. 여기서는 앞서 계산한 값들을 모두 저장한 배열인 cache라는 인수를 추가로 받는다.
fibonacciCache.c
4 /* 피보나치 수 n을 계산하는데, 앞서 계산한 값을 저장하는 캐시를 활용한다.*/
5
6 size_t fibCacheRec(size_t n, size_t cache[n]) {
7 if (!cache[n-1]) {
8 cache[n-1]
9 = fibCacheRec(n-1, cache) + fibCacheRec(n-2, cache);
10 }
11 return cache[n-1];
12 }
13
14 size_t fibCache(size_t n) {
15 if (n+1 <= 3) return 1;
16 /* 값을 캐시에 저장할 VLA를 설정한다. */
17 size_t cache[n];
18 /* VLA는 반드시 대입 연산으로 초기화해야 한다. */
19 cache[0] = 1; cache[1] = 1;
20 for (size_t i = 2; i < n; ++i)
21 cache[i] = 0;
22 /* 재귀 함수를 호출한다. */
23 return fibCacheRec(n, cache);
24 }