C language 재귀함수를 이용한 Fibonacci 수열 2020/09/16 12:07 by The 2nd

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>

/*
Fibonacci sequence
1,1,2,3,5,8,13,21,34,55,89,144, ...

*/

int fibonacci(int num);

int main()
{
for (int i = 1; i <= 15; i++)
printf("%d ", fibonacci(i));

return 0;

}

int fibonacci(int num)
{
int j, sum=0;
if ((num - 2) <= 0) return 1;

for (j = num - 2; j < num; j++)
sum += fibonacci(j);
return sum;
}

/*
아래와 같이 줄일수도 있다
int fibonacci(int num)
{
if ((num - 2) <= 0) return 1;
else
return fibonacci(num-1)+fibonacci(num-2);
}
*/


// 재귀는 메모리 효율면에서 비효율적이고 중복되는 계산이 필연적으로 따라감

덧글

댓글 입력 영역