Recursion and Dynamic Programming

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.swift 
func fib(_ n: Int, _ memo: inout [Int: Int]) -> Int {
	if let cached = memo[n] {
		return cached
	}
	if n < 2 {
		memo[n] = n
		return n
	}
	let value = fib(n - 1, &memo) + fib(n - 2, &memo)
	memo[n] = value
	return value
}

var memo: [Int: Int] = [:]
let 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

  • Swift: the recursion takes the memo as an inout [Int: Int] parameter rather than a static var, which keeps state explicit without hiding the lesson behind a shared global. The if let cached = memo[n] pattern stays parallel to the lesson spec instead of leaning on memo[n, default: …].
  • 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 `[Int: Int]` dictionary keyed by `n` stores each completed subproblem. Before recursing, check `memo[n]`: a hit returns immediately, a miss descends.
explicit memo state The memo is threaded through the recursion as `memo: inout [Int: Int]` so the lesson stays about caching, not global state.