Recursion & Divide/Conquer
- Write recursive functions with an explicit base case and a shrinking recursive case
- Trace a recursive call on the call stack and predict its maximum depth
- Draw the call tree of naive fib and explain why memoization collapses it to O(n)
- Describe the divide-and-conquer shape (split, solve halves, combine) using merge sort
- Convert a recursion to iteration with an explicit stack, and say when you must
| Spaced-rep warm-up: Days 23–26 cards + due deck | 10 min |
| ELI5 + tech read, watch the call-stack visualizer | 20 min |
| Guided: stack breathing + nested data + merge sort | 40 min |
| Practice: fast pow + flatten | 20 min |
| Project: pattern log recursion section | 20 min |
| Quiz + flashcards | 10 min |
Builds on: Day 3 — Functions & scope · Day 12 — Decorators & lru_cache · Day 25 — Stacks — the call stack's structure
A set of Russian dolls, and your job is to count them. The honest method: open the outermost doll, and inside you find… a slightly smaller version of THE EXACT SAME PROBLEM. So you apply the same move again. Eventually you reach the tiny solid doll that doesn't open — you don't recurse on it, you just say "one." That solid doll is the base case, and without it you'd be trying to open dolls forever. Then the answers reassemble on the way OUT: the innermost answer is 1, the next doll says "1 + what was inside me = 2," and so on outward until the outermost doll announces the total.
That's recursion: a function that calls itself on a *smaller* version of its problem, plus a smallest case solved directly. The half-opened dolls sitting on the table while you work inward? That's the call stack — Day 25's tray pile, holding every paused caller until its inner answer comes back. Stack too many dolls (no base case, or input too deep) and the table overflows — literally a *stack overflow*. Divide and conquer is the power move: instead of opening one doll at a time, split the problem in HALF, solve both halves the same way, and combine — halving is why these algorithms end up O(n log n) instead of O(n²).
Recursion is the native language of nested data, and your career is full of nested data: directory trees, JSON documents from every API (Day 41), abstract syntax trees, org charts — and next week's binary trees (Day 29) and graphs (Day 31) are traversed almost entirely by recursion. Merge sort's divide-and-conquer shape explains WHY sorting is O(n log n) (Day 32), and memoization is dynamic programming's front door (Day 34). Interviewers use recursion as a lens: a candidate who states the base case, the shrinking step, and the stack depth is demonstrating structured thinking, not syntax.
Russian dolls — the call stack runs fib(4)
step 1 / 6Call fib(4). A FRAME is pushed holding its local state. fib(4) can't answer yet — it needs fib(3) and fib(2) first.
Guided practice
Watch the stack breathe
20 min- In
recursion_lab.py, writecountdown(n)(print n, recurse on n−1, base case n == 0 prints "liftoff") — then add the depth-printing version from the starter that indents by call depth. Runcountdown(5)and watch the descent and return visually. - Write naive
fib(n)with a global call counter. Run fib(10), fib(20), fib(25) and record the call counts — watch the explosion (fib(25) makes ~240k calls). - Add
@functools.lru_cacheabove fib, reset the counter, rerun fib(25) — count the calls now (should be ≤ 49: each input once, plus lookups). Write the one-sentence explanation in a comment. - Trigger the safety rail on purpose: call
countdown(20_000)and read the RecursionError. Then state in a comment which conversion (plain loop) fixes it and why the loop has no such limit.
Recurse over real nested data + merge sort
20 min- Write
total_size(data): given arbitrarily nested lists of ints (e.g. [1, [2, [3, 4]], 5]), return the sum of all ints. Base case: an int. Recursive case: a list — sum the recursion over its elements. This is the JSON-walking shape you will use forever. - Write
merge_sortfrom the tech section, plus themerge(left, right)combine using Day 24's two-pointer walk. Test against Python's sorted() on 100 random lists (starter shows the harness). - In a comment, do the Day 22 accounting: levels × work-per-level = O(n log n). Then answer: what is merge sort's space complexity, and where does it go?
- Convert countdown to iteration two ways: a plain loop, and — overkill here but the general tool — an explicit stack of pending values (Day 25). The second version is the template for iterative tree traversal on Day 29.
On your own
Two solo
20 min(1) Fast exponentiation: pow_fast(x, n) for non-negative n in O(log n) multiplications. The divide: x^n = (x^(n/2))² when n is even; odd n peels one factor. Verify against x ** n and count the multiplications for n = 1000 (should be ~15, not 1000).
(2) Flatten: flatten(data) returning a flat list from arbitrarily nested lists — the total_size shape but building a list. Then state: what does the call stack's maximum depth depend on for this function (hint: nesting depth, not total length)?
Hints: for (1), recurse on n // 2 ONCE and square the result — recursing twice rebuilds the fib explosion you just escaped.
Pattern log: the recursion section
Add "Recursion & Divide/Conquer" to patterns.md: the two-part contract (base case + shrinking step) as the checklist you run on every recursive function; your solved problems (nested sum, merge sort, fast pow, flatten) with one-line notes; the fib call-count table (naive vs memoized — real numbers from your run); recognition cues ("nested", "defined in terms of itself", "sorted halves", "same problem, smaller"); and honest costs (stack depth = memory, ~1000-frame limit, when to convert to iteration + explicit stack). Close with the bridge sentence to Day 34, written in your own words: overlapping subproblems + cache = dynamic programming. Commit — Week 4's toolkit is now complete for tomorrow's drill.
Common mistakes & misconceptions
- Writing the recursive case first and the base case as an afterthought. Write the base case FIRST — it is the answer's foundation, and forgetting it is the #1 cause of RecursionError.
- Recursing on an unshrunken input (fib(n) calling fib(n)). The base case only saves you if every call moves toward it — check the shrinking step explicitly.
- Treating RecursionError as "Python is broken." The ~1000-frame limit is a memory safety rail; deep linear recursions should be loops, deep branching ones explicit stacks.
- Recursing twice on the same half in fast exponentiation (return pow_fast(x, n//2) * pow_fast(x, n//2)). That recomputation rebuilds the exponential call tree — bind the result once, then square it.
- Believing memoization is free. lru_cache trades O(n) memory (and hashable-argument requirements) for the speedup — Day 22's space column applies.
- Slicing lists in recursive calls without noticing the cost: nums[:mid] copies O(n) per level. Fine for learning merge sort; production versions pass index bounds instead.
Q1. Naive recursive fib(40) is astronomically slower than fib(20). The root cause?
Q2. Merge sort is O(n log n). Where do the two factors come from?
Q3. A recursion must process a chain of 500,000 linked nodes. In Python you should…
Go deeper — curated resources
- Why Python has no tail-call optimization — Some languages reuse the current frame for tail calls, making recursion loop-cheap. Python deliberately refuses (Guido values honest tracebacks). Knowing this explains why the "convert to a loop" rule is Python-specific advice.
- Call-count explosion measured naive vs memoized and recorded
- merge_sort passes 100 randomized tests against sorted()
- pow_fast verified O(log n) by multiplication count
- patterns.md recursion section committed; quiz ≥ 2/3
← Back: The call stack is Day 25's structure run by the interpreter; the merge step is Day 24's two pointers on Day 26's problem; lru_cache is Day 12's decorator finally showing its full power.
Forward →: Trees (Day 29) and graphs (Day 31) are traversed by exactly today's shapes. Day 32 builds on merge sort's accounting, Day 33 is divide-and-conquer with a discarded half, and Day 34 grows today's memoized-fib insight into dynamic programming proper.
Unlocks: D28 Week 4 Checkpoint: Pattern Drill · D29 Binary Trees & BSTs · D31 Graphs, BFS & DFS · D32 Sorting