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

def fib(n, memo)
	if memo.key?(n)
		return memo[n]
	end
	if n < 2
		memo[n] = n
		return n
	end
	value = fib(n - 1, memo) + fib(n - 2, memo)
	memo[n] = value
	value
end

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

Complexity

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

Implementation notes

Ruby: the recursion takes the memo as a Hash argument rather than a module-level @@memo, which keeps state explicit without hiding the lesson behind a shared global. The key? + bracket-index pair stays parallel to the lesson spec instead of leaning on a Hash.new { |h, k| h[k] = ... } block default that would hide the hit / miss branch.
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 `Hash` keyed by `n` stores each completed subproblem. Before recursing, check `memo.key?(n)`: a hit returns immediately, a miss descends.

explicit memo state The memo is threaded through the recursion as a `Hash` argument rather than a constant or global, which keeps the lesson about caching, not shared state.