[C/C++] 코드업 1915 : (재귀함수) 피보나치 수열

문제풀이

재귀함수를 사용하여 피보나치 수열을 구하면 됨. 이전 두 항의 합을 더하면 현재 항의 값이 나오게 됨.

재귀 함수 관점에서 생각하면 5번째 항이면 3번째와 4번째  항, 그리고 각각 3번째 항은 (1번째 항과 2번째 항)의 합이고, 4번째 항은 (2번째 항과 3번째 항)의 합이 됨. 이런 식으로 쪼개지고 쪼개지고 하는 것임.

 

이번 문제는 시간 제한이 2초나 되고 입력되는 자연수가 20이하이므로 재귀 함수를 편하게 구현하면 됨.

소스코드

#include <iostream>
using namespace std;

int fibbo(int a){
	if (a==1 || a==2)
		return 1;
	else
		return fibbo(a-1)+fibbo(a-2);
}

int main()
{
    int n;
    cin>>n;
    cout<<fibbo(n);
}