[C/자료구조] 재귀함수를 이용한 피보나치 수열과 반복문을 이용한 피보나치 수열

피보나치 수열이란?

피보나치 수열이란 다음과 같이 정의되는 수열이다

피보나치 수열

피보나치 수열에서는 앞의 두 개의 숫자를 더해서 뒤의 숫자를 만든다.

정의에 따라 수열을 만들어 보면 다음과 같다.

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

 

피노나치 수열은 이탈리아 수학자 피보나치(Fivonacci)가 발견한 수열로서 한 쌍의 토끼가 번식하는 상황을 수열로 만든 것이다. 피보나치 수열은 수학과 과학의 많은 분야에서 사용되고 있다.

피보나치 수열 그림

피보나치 수열은 정의 자체가 순환적으로 되어 있다. 따라서 구현 시에 순환 호출을 사용하는 것이 자연스러운 방법이다. 피보나치 수열을 재귀함수로 이용하여 프로그램해 보면 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int Fibonacci(int n) {
	if (n == 0)
		return 0;
	else if (n <= 1)
		return 1;
	
	return Fibonacci(n - 1) + Fibonacci(n - 2);
}

int main(void) {
	int n;
	int i;

	printf("피보나치 수열의 개수 : ");
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		printf("%d ", Fibonacci(i));
	}
	
	return 0;
}

재귀함수 피보나치 수열

 

위의 함수는 매우 단순하고 이해하기 쉽지만 매우 비효율적이다.

예를들어 Fibonacci(6)으로 호출하였을 경우 Fibonacci(4)가 두 번이나 계산되기 때문이다. Fibonacci(3)은 3번 계산되고 이런 현상은 순환호출이 깊어질수록 점점 심해진다. 따라서 상당히 비효율적임을 알 수있다.

재귀함수 피보나치 수열의 비효율성

순환적인 피보나치의 수열 알고리즘의 시간 복잡도는 어떻게 될까?

순환적인 알고리즘의 복잡도는 순환적으로 표현할 수 있다.

 

                          T(n) = T(n-1) + T(n-2) + C

 

위의 순환적인 수식을 풀어보면 대략 다음과 같은 시간 복잡도가 도출된다.

 

                                         O(2^n)

 

그렇다면 피보나치 수열을 계산하는데 다른 방법이 있을까?

이 경우에는 순환을 사용하지 않고 반복구조를 이용하여 프로그램하면 가장 좋은 결과를 얻을 수 있다.

피보나치 수열을 반복문으로 이용하여 프로그램해 보면 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {
	int f1 = 0;
	int f2 = 1;
	int result = 0;
	int n;

	printf("피보나치 수열의 개수 : ");
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		if (i == 0) {
			printf("%d ", f1);
		}
		else if (i == 1) {
			printf("%d ", f2);
		}
		else {
			result = f1 + f2;
			printf("%d ", result);
			f1 = f2;
			f2 = result;
		}
	}

	return 0;
}

반복문 피보나치 수열

 

for문을 사용하였기 때문에, 피보나치 수열을 계산하는 반복 알고리즘의 시간 복잡도는 O(n)이다.
문제의 정의가 순환적으로 되어있는 경우에도 순환 알고리즘보다 반복 알고리즘의 효율성이 뛰어날 수 있다는 것을 알 수 있다.