Recursion Trees and Memoization

When one call makes two calls

#include <iostream>
using namespace std;

long long calls = 0;

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

int main() {
    for (int n : {10, 20, 25}) {
        calls = 0;
        long long f = fib(n);
        cout << "fib(" << n << ") = " << f << " using " << calls << " calls" << endl;
    }
    return 0;
}

Output

fib(10) = 55 using 177 calls
fib(20) = 6765 using 21891 calls
fib(25) = 75025 using 242785 calls

The calls form a recursion tree full of repeats: fib(3) is worked out again and again. That's about O(2ⁿ).

Memoization: remember answers

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

vector<long long> memo(91, -1);
long long calls = 0;

long long fib(int n) {
    calls++;
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

int main() {
    cout << fib(90) << " using " << calls << " calls" << endl;
    return 0;
}

Output

2880067194370816120 using 179 calls

Think of it like this: If a friend asks “what's 37 × 49?” three times, you work it out once and remember it.

Remember: If a recursive function solves the same smaller problem many times, memoize it. This is the first step to dynamic programming (Module 17).