피보나치 수열(C++)

n을 입력받아 n번째 피보나치 수의 값을 구하시오.(n은 최대 45까지이다.)


두가지 방법으로 풀었다.

<method1>
#include <iostream>
#include <windows.h>

using namespace std;
int main(){
   
    int n,i,p[45]={1,1,};
   
    cin>>n;
   
    for(i=2;i<n;i++)p[i]=p[i-1]+p[i-2];
   
    cout<<p[n-1]<<endl;
   
    system("PAUSE");
   
    return 0;
}

실행결과
10
55
Press any key to continue . . .


<method2>
재귀 호출함수를 사용하여 메모리를 많이 사용하게 되고 그많큼 속도도 느려진다. 높은 숫자를 입력한다면, 스택오버플로우가 발생할 것이다.

#include <iostream>
#include <windows.h>

using namespace std;
int fibo(int n);
int main(){
   
    int n;
   
    cin>>n;
    cout<<fibo(n)<<endl;
   
    system("PAUSE");
   
    return 0;
}
int fibo(int n){
   
    if(n==1)return 1;
    else if(n==2)return 1;
    else return fibo(n-1)+fibo(n-2);
}

실행결과
15
610
Press any key to continue . . .

입력값이 40을 넘어가는 순간부터 계산속도가 현저히 느려진다.
50은 한참을 기다려도 결과가 나오질 않는다.