Fibonacci with Memoization

Compute fib(n) recursively and cache each fib(k) in a memo map so each subproblem is solved at most once. Turns exponential recursion into a linear walk, the canonical introduction to dynamic programming.

Algorithm

Canonical input n = 6 produces fib(6) = 8. The replay shows the descent for fib(6) -> fib(5) -> ... -> fib(0) then four cache hits on the unwind (one per repeat-call subproblem).

Basic Implementation

basic.py

def fib(n, memo):
    if n in memo:
        return memo[n]
    if n < 2:
        memo[n] = n
        return n
    value = fib(n - 1, memo) + fib(n - 2, memo)
    memo[n] = value
    return value

memo = {}
result = fib(6, memo)
print(result)
print(memo)

Complexity

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

Implementation notes

Python: pass memo explicitly. Do not use functools.lru_cache; it would hide the memo write and the cache-hit branch.
The replay shows each fib(k) call and the memo state after, marking the cache-hit steps distinctly so the viewer can count how many descents were avoided.

memoization Reuse cached subproblem results instead of re-descending.