[백준 10870] 피보나치 수 5

팩토리얼 문제와 달리 이번 문제는 친절하게 점화식이 나왔다. 이를 이용해서 재귀로 작성해보자.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

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

int main()
{
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
	
    cout << fibo(n);
	
    return 0;
}