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

local function fib(n, memo)
	if memo[n] ~= nil then
		return memo[n]
	end
	if n < 2 then
		memo[n] = n
		return n
	end
	local value = fib(n - 1, memo) + fib(n - 2, memo)
	memo[n] = value
	return value
end

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

Complexity

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

Implementation notes

Lua: the recursion takes the memo as a parameter rather than as an upvalue or a module-level cache, which keeps state explicit without hiding the lesson behind a shared global. Tables pass by reference, so the recursive calls share the same memo without an explicit return-the-memo dance.
memo[n] ~= nil is the explicit cache-check predicate; Lua's table-default behaviour returns nil for absent keys, so the predicate stays parallel to the lesson spec instead of leaning on metatable defaults.
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 table `memo` keyed by `n` stores each completed subproblem. Before recursing, check `memo[n] ~= nil`: a hit returns immediately, a miss descends.

explicit memo state The memo is threaded through the recursion as the second parameter so the lesson stays about caching, not a closure upvalue.