피보나치 수열(재귀함수) 알고리즘

피보나치 수열 알고리즘

피보나치 수열 알고리즘이란?

- 첫번째 항의 값이 0이고 두 번째 항의 값이 1일때, 이후의 항들은 이전의 두 항을 더한 값으로 이루어지는 수열을 말한다.

ex) 0 1 1 2 3 5 8 13 21 34 55 89 ....

#include <iostream>
using namespace std;

void Fibonacci(int *PtrFibonacci, int Max);
void print(int *PtrFibonacci, int Max);

int main()
{
	int *PtrFibonacci;
	int Num;

	cout << "몇개의 수를 구할까요? : "; cin >> Num;
	PtrFibonacci = new int[Num]; // 피보나치 수열을 저장하기 위한 동적할당

	Fibonacci(PtrFibonacci, Num); // 피보나치 수열 함수
	print(PtrFibonacci, Num);
	delete[] PtrFibonacci;
}

void Fibonacci(int *PtrFibonacci, int Max)
{
	PtrFibonacci[0] = 0;
	PtrFibonacci[1] = 1;
	for (int i = 2; i < Max; i++)
		PtrFibonacci[i] = PtrFibonacci[i - 1] + PtrFibonacci[i - 2];
}
void print(int *PtrFibonacci, int Max)
{
	for (int i = 0; i < Max; i++)
		cout << i + 1 << " = " << PtrFibonacci[i] << endl;
}

피보나치 수열 알고리즘은 위와 같다.

22행부터 설명을 하자면,

피보나치는 0과 1로 시작을 해서 두 숫자를 더하게 만든다.

입력 받은 숫자만큼 FOR(반복문)을 반복한다.

앞에서 말했듯이 "이후의 항들은 이전의 두 항을 더한 값으로 이루어 진다" 라고 했다.

ptr[i] = ptr[i-1] + ptr[i-2];가 된다.

처음에 10을 입력했다고 치고 프로그램이 돌아가는 과정을 적어보자.

ptr[0] = 0;

ptr[1] = 1;

ptr[2] = ptr[1] + ptr[0];

ptr[3] = ptr[2] + ptr[1];

ptr[4] = ptr[3] + ptr[2];

ptr[5] = ptr[4] + ptr[3];

ptr[6] = ptr[5] + ptr[4];

ptr[7] = ptr[6] + ptr[5];

ptr[8] = ptr[7] + ptr[6];

ptr[9] = ptr[8] + ptr[7];

이런 형식이 된다.

그럼 이제 재귀적 함수 호출을 이용해서 피보나치 수열 코드를 짜보자.

#include <iostream>
using namespace std;

int fibonacci(int n);

int main()
{
	int n;
	cout << "몇 번 돌릴거야? : "; cin >> n;
	for (int i = 0; i < n; i++)
		cout << fibonacci(i) << endl;
}

int fibonacci(int n)
{
	if (n == 0 || n == 1) // 재귀 함수가 끝나는 종료 조건
		return n;
	else
		return fibonacci(n - 1) + fibonacci(n - 2);

	//한 줄로 줄이자면
	// return (n == 0 || n == 1) ? n : fibonacci(n-1) + fibonacci(n-2);
}

14행 함수는 재귀적 함수를 이용해서 피보나치 수열 기능을 하고있다.

16행은 재귀 함수가 끝나는 종료 조건이고

18행은 재귀 함수가 시작되는 것이다.

fibonacci 함수 몸체를 한 줄로 줄이자면

return (n == 0 || n == 1) ? n : fibonacci(n-1) + fibonacci(n-2); 가 된다.

하지만 재귀함수는 스택을 이용해서 하는것이기에 스택 오버플로우를 조심해야 된다.