피보나치 수는 급격히 커지는데, 순서대로 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 377, 610, 987 등이다.

다음 황금률(golden ratio)을 이용하여

(7.6)

다음이 성립함을 증명할 수 있다.

(7.7)

이 식을 점근 표기법으로 표현하면 다음과 같다.

(7.8)

이처럼 F_n은 지수적으로 증가한다.

이 재귀식을 다음과 같이 C 함수로 쉽게 바꿀 수 있다.

fibonacci.c

4 size_t fib(size_t n) {

5   if (n < 3)

6     return 1;

7   else

8     return fib(n-1) + fib(n-2);

9 }