[ 피보나치 수열 ] 귀납법과 반복법

 피보나치수열 & 귀납법의 장단점 

1. 귀납법 사용

int Fibonacci1(int num)

{

//주어진 항 n이 1이거나 그보다 작은 경우 return.

if (num <= 1)

{

return num;

}

else

{

// 잘 생각해보면 피보나치 수열의 귀납식은 수행하는 과정에서 같은 내용을 또 연산하게된다.

// 재귀식은 코드길이를 짧아지게 하고, 보다 간편하게 소스를 구성할 수 있지만

// 피보나치 수열의 경우처럼 불필요한 연산을 수행할 수 있다.

// num값이 늘어나면 기하급수적으로 중복 연산량이 발생하고, 

// StackOverflow로 프로그램이 죽어버릴 수가 있다. 

return Fibonacci1(num - 1) + Fibonacci1(num - 2);

}

}

2. 반복법 사용

//이를 해결하기 위해 피보나치 반복적 방법이 있습니다. 

int Fibonacci2(int num)

{

long answer = 0;

long f0 = 0;

long f1 = 1;

for (int i = 1; i < num; i++)

{

answer = f0 + f1;

f0 = f1;

f1 = answer;

}

return answer;

}

void main()

{

cout << Fibonacci1(5) << endl;

cout << Fibonacci2(5) << endl;

}