피보나치 함수를 재귀함수로 만들면
1. fib(n) = fib(n-1) + fib(n-2)
2. 1의 fib(n-1)을 계산하기 위해 fib(n-2)랑 fib(n-3)을 계산하고,
3. 1의 fib(n-2)를 계산하기 위해 fib(n-3)이랑 fib(n-4)를 계산하고
4. 2의 fib(n-2)를 계산하기 위해 fib(n-3)이랑 fib(n-4)를 계산하고 (3이랑 똑같은데 계산 한번 더 해야 함)
...
결론적으로 fib(n-1)이 1번, fib(n-2)가 2번, fib(n-3)을 3번, f(n-4)를 5번, f(n-5)가 8번, ... n이 커질수록 계산 횟수가 기하급수적으로 증가하게 되므로 지금 사용하신 방법보다는 반복문으로 구하는 것이 훨씬 효율적입니다.
재귀함수로 풀기 위해서는 다음주에 배열을 배우고 나서 아래 코드를 활용하여 다시 도전해보세요.
i번째 피보나치 수를 store_fibonacci[i]에 저장해서 빠르게 계산할 수 있습니다. 메모이제이션 기법이라고 불러요
#include <stdio.h>
long long store_fibonacci[10000]={0, 1, 1, 2, 3, 5, 8, 13}; // 사실 0, 1까지만 써도 됨. store_fibonacci[i]= (i번째 피보나치 수)
long long calculate_fibonacci(long long n) {
if (store_fibonacci[n]==0) store_fibonacci[n] = calculate_fibonacci(n-2) + calculate_fibonacci(n-1); // 이전에 계산했던 게 없으면 새로 계산해서 배열에 저장함
return store_fibonacci[n]; // 이전에 계산했던 값을 불러옴
}
int main() {
for (int n = 1; n < 90; n++) printf("%lld\n", calculate_fibonacci(n));
return 0;
}
