중앙댿� 자료구조 피보나치 수열의 계산-Memoization

(1)recursive call 을 이용한 code

#include <stdio.h>
//recursion 으로 구현
FILE * fp;
int fibo(int n){
if ( n == 0 ) return 0;
else if(n == 1) return 1;
else return fibo(n-1) + fibo(n-2);
}
int main(void) {
fp= fopen("C:\\temp\\result.txt","wt");
int num;
scanf("%d",&num);
fprintf(fp,"%d\n",num);
printf("결과는 %d\n",fibo(num));
fprintf(fp,"결과는 %d\n",fibo(num));
return 0;
}

<출력파일>
12
결과는 144

(2)recursive call with memoization을 이용한 code

#include <stdio.h>
//recursion with memorization으로 구현
int memo[100]= {0,1};
FILE *fp;
int fibo(int n){
int f; if(memo[n]!= 0) return memo[n];
else if( n == 0 )
return 0;

else if(n == 1)
return 1;

else {
f= fibo(n-1) + fibo(n-2);
memo[n] = f;
return f;
}
}
int main(void) {
int num; fp= fopen("C:\\temp\\result.txt","wt");
scanf("%d",&num);
fprintf(fp,"%d\n",num);

printf("결과는 %d\n",
fibo(num)); fprintf(fp,"결과는 %d\n",fibo(num));
return 0;
}

<출력파일>
14
결과는 377