Module 5
Recursion & memoization
A recursive function is a proof by induction wearing a code costume. Designing one is always the same three moves: (1) the base case — the input so small the answer is immediate; (2) the shrink — express the problem in terms of a strictly smaller version of itself; (3) trust the call— assume the recursive call returns the right answer for the smaller input, and build your answer from it. The classic beginner trap is trying to mentally trace every nested call. Don't — verify the base case, verify one step of the shrink, and induction does the rest.
The machine's side of the bargain: every active call sits in a stack frame holding its locals, so recursion depth is memory — O(depth) space even if you allocate nothing — and past a few thousand frames you get a stack overflow. Depth-first recursion on a balanced tree costs O(log n) stack; on a degenerate (linked-list-shaped) tree, O(n). Any recursion can be rewritten with an explicit stack, and deep linear recursions usually should be — say so before the interviewer asks.
🎛 Naive vs memoized — count the calls
Naive recursion — O(2ⁿ)
177
function calls — fib(8) alone is recomputed from scratch inside fib(9)
With memoization — O(n)
19
calls — every subproblem solved once, then read from the cache
green bar = memoized work as a fraction of naive work (11%)
Slide n up: the naive count roughly doubles each step— the signature of overlapping subproblems. Saying “I'll memoize because the subproblems overlap” out loud, before you're asked, is one of the cheapest strong signals you can send in a technical conversation.
Worked example — from exponential to linear in three lines
def fib(n): # naive: O(2^n) — fib(n-2) computed twice,
if n < 2: return n # fib(n-3) four times, and so on
return fib(n-1) + fib(n-2)
def fib_memo(n, memo={}): # memoized: O(n) time, O(n) space
if n < 2: return n
if n not in memo:
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]The structure of the function didn't change — only “have I solved this exact subproblem before?” was added. That question is worth asking of every recursion you write: if subproblems repeat (overlapping subproblems), memoize; if they also combine optimally, you've re-derived dynamic programming — memoization is top-down DP.
Where recursion is the natural first draft
- Trees — almost every tree problem is “solve for left child, solve for right child, combine” (next module).
- Divide & conquer — merge sort, quicksort, binary search are one recursive idea each.
- Backtracking — permutations, subsets, N-queens: choose, recurse, un-choose.
- Nested or self-similar input — JSON, file systems, expression parsing.
Say it out loud
- “Base case first: empty tree returns zero. Then each node trusts its children's answers.”
- “These subproblems overlap — fib(n−2) is computed inside both branches — so memoizing takes this from O(2ⁿ) to O(n).”
- “Recursion depth is O(n) here, which risks stack overflow on large inputs — I'd convert to iteration with an explicit stack in production.”