백준 10870 - 피보나치 수 5

문제 설명

이제까지는 for문으로 피보나치를 구현하였다. 이럴 때의 문제는 숫자가 커질수록 걸리는 시간이 기하학적으로 커지는 것이다. 

이럴 때 해결 방법은 재귀의 방법이다. 

 

재귀를 통한 방법을 알고리즘으로 구현하여 구성한다. 

 

#include <iostream>
using namespace std;

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

int main() {
    int N;
    cin>>N;
    cout<<fibonacci(N)<<'\n';
    return 0;
}