저장 공간이 줄어드는 대신 계산 시간을 절약하도록 재귀 함수를 구현하면 처음 계산하는 피보나치 수에 대해서만 재귀호출이 실행된다. 따라서 fibCache(i)가 실행되는 시간은 n에 대해 선형적으로 증가한다.

T_fibCache(n) = n·C₃

(7.13)

여기서 C₃은 플랫폼 종속적인 매개변수다.^{Exs 3} 피보나치 수를 구하는 알고리즘을 살짝 수정하기만 해도 지수적으로 증가하던 실행 시간을 선형적으로 증가하게 만들 수 있다. 구체적인 구현 설명과 실행 시간을 실제로 측정하는 방법은 생략한다.^{Exs 4}

TAKEAWAY 7.17 알고리즘이 나쁘면 성능이 좋은 구현 코드가 나올 수 없다.

TAKEAWAY 7.18 알고리즘을 개선하면 성능을 급격히 개선시킬 수 있다.

이번에는 재미 삼아 피보나치 수를 구하는 세 번째 구현 방식을 살펴보자. fib2Rec 함수는 VLA(Variable-Length Array) 대신 FLA(Fixed-Length Array)를 사용한다.

fibonacci2.c

 4 void fib2rec(size_t n, size_t buf[2]) {

 5   if (n > 2) {

 6     size_t res = buf[0] + buf[1];

 7     buf[1] = buf[0];

 8     buf[0] = res;

 9     fib2rec(n-1, buf);

10   }

11 }

12

13 size_t fib2(size_t n) {

14   size_t res[2] = { 1, 1, };

15   fib2rec(n, res);

16   return res[0];

17 }