C언어 - 피보나치 예제와 재귀 호출의 장단점

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

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

	맨앞의 숫자는 1
	두번째 숫자는 1
	세번째 숫자는 맨앞의 수 그리고 그앞의 수 1을 더해서 2
	네번째는 세번째 숫자2와 두번째 숫자 1을 더해 3
	다섯번째 숫자 5는 2+3의 결과
	.......

	고로 자기 앞앞의 숫자와 앞의 숫자를 더한것.

	ex) fibonacci(5) = 3 + 2 = fibonacci(4) + fibonacci(3)
	ex) fibonacci(6) = 8 = 5 + 3 = fibonacci(5) + fibonacci(4)

*/

int fibonacci(int number);


int main() {

	for (int count = 1; count < 13; ++count)
		printf("%d ", fibonacci(count));

	return 0;
}

int fibonacci(int number) {
	printf("fibonacci with %d\n", number);

	if (number > 2)
		return fibonacci(number - 1) + fibonacci(number - 2); // double recursion
	else
		return 1;
	
}
/*단점 :
1.메모리를 많이 쓴다(호출할때 마다 number파라미터가 쌓이기 때문)
2. 파라미터뿐아니라 호출한 함수도 쌓인다. 
3 .중복계산을 하게 된다.
*/

 

3. 중복계산은 아래와 같이 발생.

 

fibonacci with 1
1 fibonacci with 2
1 fibonacci with 3
fibonacci with 2
fibonacci with 1
2 fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
3 fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
5 fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
8 fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
13 fibonacci with 8
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
21 fibonacci with 9
fibonacci with 8
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
34 fibonacci with 10
fibonacci with 9
fibonacci with 8
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 8
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
55 fibonacci with 11
fibonacci with 10
fibonacci with 9
fibonacci with 8
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 8
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 9
fibonacci with 8
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
89 fibonacci with 12
fibonacci with 11
fibonacci with 10
fibonacci with 9
fibonacci with 8
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 8
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 9
fibonacci with 8
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 10
fibonacci with 9
fibonacci with 8
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 8
fibonacci with 7
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 6
fibonacci with 5
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 4
fibonacci with 3
fibonacci with 2
fibonacci with 1
fibonacci with 2
144

 

 

 

출처 : 홍정모의 따라배우는 C언어