#include <iostream>
#include <map>
using namespace std;

int fibonacci(int x) {
    return (x <= 1) ? x :
        fibonacci(x - 1) + fibonacci(x - 2);
}

template<typename I, typename U>
function<U(I)> memoize(U (*fun)(I)) {
    map<I, U>  memo;
    return [fun, memo](I x) mutable -> I {
        if (memo.find(x) != memo.end()) {
            return memo[x];
        }
        U r = fun(x);
        memo[x] = r;
        return r;
    };
}

auto memFibonacci = memoize<int, int>(fibonacci);
for (int i = 1; i < 3; i++) {
    time_t start = time(0);
    int f40 = memFibonacci(40);
    long seconds = time(0) - start;

    cout << i << ": f40 is " << f40 << "\n";
    cout << i << ": seconds is " << seconds << "\n";
}
// prints:
// 1: f40 is 102334155
// 1: seconds is 1
// 2: f40 is 102334155
// 2: seconds is 0

time_t start = time(0);
int f41 = memFibonacci(41);
long seconds = time(0) - start;

cout << "f41 is " << f41 << "\n";
cout << "seconds is " << seconds << "\n";
// f41 is 165580141
// seconds is 3