피보나치 예제와 재귀 호출의 장단점

예제

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

// fibonacci sequence
// 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...,

#define num1 1
#define num2 1

int fibonacci(int number)
{
	int ans;
	if (number == 1)
		return ans = num1;
	else if (number == 2)
		return ans = num2;
	else
		return ans = (fibonacci(number - 1) + fibonacci(number - 2));
}

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

	return 0;
}

성공했다. 처음 작동이 실패했던건, fibonacci()함수의 if문각각에 return을 정해주지 않았는데, 그래서 재귀호출당시 number==1이더라 내보낼 return이 없어서 쓰레기값이 나가느라 그랬던 것 같다.(왜냐하면 쓰레기값들의 피보나치가 되었었다.)

int fibonacci(int number)
{
	if (number > 2)
		return (fibonacci(number - 1) + fibonacci(number - 2));
	else
		return 1;
}

홍정모님의 코드.. 훨씬 간결하고 변수도 하나 덜 썼다…

재미있는건 저 알고리즘으로 피보나치 40정도만 구해도 콘솔창이 버벅인다는 점이다.

피보나치 40을 구하기 위해 홍정모님의 코드는 f5를 누르고나서 종료되기까지 7.72초가 걸렸고, 내 코드는 8.29초가 걸렸다… 변수 하나가 더 있어서 그런가?

그리고 위의 코드에서처럼 return에 fibonacci()함수를 두개 쓰는걸 double recursion이라고 표현한다고 한다.

위의 코드처럼 재귀함수를 수학적인 정의처럼 사용하면 코드는 간결해지지만 단점은 명확하다. 우선 계산이 중복되고, 메모리가 많이 쓰인다고 함.

int number가 커질수록 스택에 변수가 많이 쌓이고, 그리고 함수역시 스택에 엄청나게 쌓이게 됨.

이는 저 코드가 fibonacci(n)을 구할때마다 전에 남아있던 데이터를 활용하는게 아니라 계산을 처음부터 끝까지 다시 하기 때문인 듯 그래서 스택에 많은 변수가 쌓이고, 계산도 계속 중복함.

계산한 값들을 저장해서 재활용하는건 배열(array)를 배워야 함.

구현이 간결해지면, 비효율적이고 중복계산(redundant conputation)이 늘어난다는 모순이 있다고 함.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ