[자료구조] 피보나치 수열

오늘은 피보나치 수열에 대해 알아보자.

 

점화식에 대한 정의는 F(0)​=0, F(1)​=1, F(n+2)​=F(n+1​)+F(n)​ 과 같다.

 

(0) 1 1 2 3 5 8 13 21 ... 과 같이 나타내며 다음 항은 13 + 21 로 34가 나옴을 알 수 있다.

 

피보나치 수열도 재귀함수로 표현하면 간단하지만 그 전에 반복문으로 한번 프로그래밍 해보자~

 

#include <stdio.h>

int Fibo(int n) {
	int arr[100];

	arr[0] = 0; arr[1] = 1;

	for (int i = 2; i <= n; i++) {
		arr[i] = arr[i - 1] + arr[i - 2]; //점화식 활용
	}

	return arr[n];
}

 

자 보시다시피 반복을 통해 다음 항을 구하는 방식이다. 다음은 재귀적으로 구현해보자

 

#include <stdio.h>

int Fibo(int n) {
	if (n == 0)
		return 0;  //0번째 항은 0
	else if (n == 1)
		return 1;  //1번째 항은 1
	else
		return Fibo(n - 1) + Fibo(n - 2);  //점화식 활용
}

 

반복문 보다 간단하다는 것을 알 수 있다.