#include <iostream>
#include <utility>
#include <cassert>

using namespace std;

// return {fib_(n - 1), fib_n}
pair<int, int> fib_impl(unsigned int n) {
    if (n == 0) return {1, 0};
    if (n == 1) return {0, 1};
    auto p = fib_impl(n - 1);
    return {p.second, p.first + p.second};
}

int fib(unsigned int n) {
    return fib_impl(n).second;
}

int main() {
    assert(fib(2) == 1);
    assert(fib(10) == 55);
}