// Contoh Bab 06: Fibonacci rekursif yang lambat dan versi perulangan.
//
// Compile:  g++ -std=c++17 -O2 -o fib exercises/06/04-fibonacci.cpp
// Jalankan: ./fib
// Lalu ketik n, misalnya 30, lalu coba lagi dengan 40 dan 45.

#include <iostream>
using namespace std;

long long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

long long fib_cepat(int n) {
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return a;
}

int main() {
    int n;
    cin >> n;

    cout << "versi perulangan: " << fib_cepat(n) << "\n";
    cout << "versi rekursif (sabar untuk n besar): " << fib(n) << "\n";
    return 0;
}