Fibonacci with Memoization

Compute fib(n) recursively. Cache each fib(k) in a memo map so each subproblem is solved at most once.

Algorithm

Canonical input n = 6 produces fib(6) = 8. Replay highlights every memo write and every cache hit.

Basic Implementation

basic.cpp

#include <iostream>
#include <map>

int fib(int n, std::map<int, int>& memo) {
    auto it = memo.find(n);
    if (it != memo.end()) {
        return it->second;
    }
    if (n < 2) {
        memo[n] = n;
        return n;
    }
    int value = fib(n - 1, memo) + fib(n - 2, memo);
    memo[n] = value;
    return value;
}

int main() {
    std::map<int, int> memo;
    int result = fib(6, memo);
    std::cout << result << std::endl;
    std::cout << "{";
    bool first = true;
    for (const auto& kv : memo) {
        if (!first) std::cout << ", ";
        std::cout << kv.first << ": " << kv.second;
        first = false;
    }
    std::cout << "}" << std::endl;
    return 0;
}

Complexity

Time: O(n) with memoization (vs. O(2^n) without)
Space: O(n) memo + O(n) call stack

Implementation notes

C++: std::map<int, int> memo; passed by reference to fib(int n, std::map<int, int>& memo). The ordered map keeps the printout deterministic so the lesson can show the final memo state honestly.
The replay shows the call stack on one side and the memo map on the other so memo writes and cache hits are visually distinct.

memoization A `std::map<int, int>` cache stores each completed subproblem. Before recursing, check the memo: a hit returns immediately, a miss descends.

explicit memo parameter Pass the memo as an explicit reference parameter so the lesson stays about caching, not language-level scoping.