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.php

<?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";

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.

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.