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.

memoization An associative array `$memo` keyed by `$n` stores each completed subproblem. Before recursing, check `array_key_exists($n, $memo)`: a hit returns immediately, a miss descends.

explicit memo state The memo is threaded through the recursion as `&$memo` so the lesson stays about caching, not global state.

Basic Implementation

                            basic.php
                        
Replay: real traced execution (multi-file project)

                            <?php
function fib($n, &$memo) {
	if (array_key_exists($n, $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);
echo $result . "\n";

                        
1$memo ← {}, action ← miss -> descend fib(5)⋯9}10$value = fib($n - 1, $memo) + fib($n - 2, $memo);11$memo[$n] = $value;⋯values this step{}$memomiss -> descend fib(5)action6$n
2$memo ← {}, action ← miss -> descend fib(4)⋯9}10$value = fib($n - 1, $memo) + fib($n - 2, $memo);11$memo[$n] = $value;⋯values this step{}$memomiss -> descend fib(4)action5$n
3$memo ← {}, action ← miss -> descend fib(3)⋯9}10$value = fib($n - 1, $memo) + fib($n - 2, $memo);11$memo[$n] = $value;⋯values this step{}$memomiss -> descend fib(3)action4$n
4$memo ← {}, action ← miss -> descend fib(2)⋯9}10$value = fib($n - 1, $memo) + fib($n - 2, $memo);11$memo[$n] = $value;⋯values this step{}$memomiss -> descend fib(2)action3$n
5$memo ← {}, action ← miss -> descend fib(1)⋯9}10$value = fib($n - 1, $memo) + fib($n - 2, $memo);11$memo[$n] = $value;⋯values this step{}$memomiss -> descend fib(1)action2$n
6$memo ← {1: 1}, action ← base 1; memo[1] = 1; return⋯9}10$value = fib($n - 1, $memo) + fib($n - 2, $memo);11$memo[$n] = $value;⋯values this step{1: 1}$memobase 1; memo[1] = 1; returnaction1$n
7$memo ← {0: 0, 1: 1}, action ← base 0; memo[0] = 0; fib(2)=1; memo[2] = 1⋯9}10$value = fib($n - 1, $memo) + fib($n - 2, $memo);11$memo[$n] = $value;⋯values this step{0: 0, 1: 1}$memobase 0; memo[0] = 0; fib(2)=1; memo[2] = 1action0$n
8$memo ← {0: 0, 1: 1, 2: 1, 3: 2}, action ← hit 1; fib(3)=2; memo[3] = 2⋯9}10$value = fib($n - 1, $memo) + fib($n - 2, $memo);11$memo[$n] = $value;⋯values this step{0: 0, 1: 1, 2: 1, 3: 2}$memohit 1; fib(3)=2; memo[3] = 2action1$n
9$memo ← {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}, action ← hit 1; fib(4)=3; memo[4] = 3⋯9}10$value = fib($n - 1, $memo) + fib($n - 2, $memo);11$memo[$n] = $value;⋯values this step{0: 0, 1: 1, 2: 1, 3: 2, 4: 3}$memohit 1; fib(4)=3; memo[4] = 3action2$n
10$memo ← {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5}, action ← hit 2; fib(5)=5; memo[5] = 5⋯9}10$value = fib($n - 1, $memo) + fib($n - 2, $memo);11$memo[$n] = $value;⋯values this step{0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5}$memohit 2; fib(5)=5; memo[5] = 5action3$n
11$memo ← {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8}, action ← hit 3; fib(6)=8; memo[6] = 8⋯9}10$value = fib($n - 1, $memo) + fib($n - 2, $memo);11$memo[$n] = $value;⋯values this step{0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8}$memohit 3; fib(6)=8; memo[6] = 8action4$n
12stdout ← 8⋯16$result = fib(6, $memo);17echo $result . "\n";values this step8stdout8$result

Complexity

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

Implementation notes

PHP: the recursion takes the memo as a by-reference associative array rather than a static cache or a class property, which keeps state explicit without hiding the lesson behind a shared global. The array_key_exists + index pair stays parallel to the lesson spec instead of leaning on $memo[$n] ?? null.
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.