피보나치수열 Fibonacci Sequence

피보나치 수열은 0 1 1 2 3 5 8 13 21 ... 와 같이 전개되는 수열로서 재귀적인 형태를 띤다.

재귀적인 형태를 띠므로 재귀 함수를 통해 구현할 수 있는데, 코드는 다음과 같다.

#include <stdio.h>

int main(void)
{
	for (int i = 0; i < 20; i++)
	{
		printf("%d ", fibonacci(i + 1));
	}
	return 0;
}

int fibonacci(int value)
{
	if (value == 1) return 0;
	else if (value == 2) return 1;
	else return fibonacci(value - 1) + fibonacci(value - 2);
}

 

피보나치 수열은 1번째는 0, 2번째는 1의 값을 반환하고 3번째 이후부터는 자신 앞의 두 개의 값을 더한 값을 반환한다.

그러므로 finonacci 함수에서 value가 1일 때는 0을 2일 때는 1을 반환하고, 3번째 이후부터는 자기 자신을 호출하는 재귀를 통해서 value - 1번째와 value - 2번째 값을 구해서 더해준다. ( 즉 자신 앞의 두 개의 값을 더한 값 )