A function that calls itself sounds like a trick. It is actually one of the deepest ideas in computing — the way a problem can solve itself by trusting a smaller copy of itself. We build it from zero, watch the machine's memory grow and shrink in real time, and end by writing a real recursion an interviewer would ask for.
if, a return, a function call). That's it. No math beyond multiplication.Picture a set of Russian nesting dolls — matryoshka. You want to know how many dolls there are in total. You open the outermost doll. Inside is… a smaller doll. You open that one. Inside is a smaller one still. You keep going until you reach the tiniest solid doll that does not open. Then you count back up.
Now notice the shape of that task. "Count the dolls in this stack" is not really one job. It is the same job wearing a smaller hat: "count the dolls in the stack I find inside, then add one for the doll I'm holding." The problem contains a smaller copy of itself. That property has a name: the problem is self-similar.
Whenever a problem is self-similar, there is a way to solve it that feels almost like cheating. You write a single instruction that says: "to solve this, peel off one layer, then solve the slightly smaller version the exact same way." A function that solves a problem by calling itself on a smaller version of that problem is called a recursive function. Recursion is just self-similarity turned into code.
This lesson is built around a real interview-style question from Stanford's AA174A pre-knowledge assessment. It asks you to write a function even_factorial(n) that returns the product of all even integers from 1 up to and including n. So even_factorial(7) multiplies 2 × 4 × 6 = 48 (we stop at 6 because 7 is odd, and the next even number, 8, is past 7). The factorial of 0 and 1 are both defined as 1. The catch: no loops, no global variables. You must use recursion.
That "no loops" rule is the heart of the matter. A loop is the obvious tool here — "go through the numbers, multiply the even ones." So why would anyone ban the obvious tool? Because the point of the exercise is not to compute a product. It is to check whether you can think recursively. Let us first feel why a loop can feel awkward for self-similar problems.
A loop is fundamentally a bookkeeping machine. To multiply the even numbers with a loop, you must invent and maintain extra variables that have nothing to do with the problem itself — an accumulator to hold the running product, and a counter to march through the numbers:
# The loopy way — works, but look at all the bookkeeping def even_factorial_loop(n): product = 1 # accumulator — extra state we invented k = 2 # counter — more extra state while k <= n: product = product * k k = k + 2 # manually step to the next even number return product
It works. But the product and the k are scaffolding — they exist only to simulate memory across iterations. The loop has no natural memory of its own, so you bolt some on. For a self-similar problem this scaffolding is noise; it hides the one clean idea underneath. The recursive version, which we will build, has no accumulator and no counter. The structure of the code will simply be the structure of the problem.
Before we write a single recursive line, let's watch self-similarity happen. Below, each doll opens to reveal a smaller doll, and the count comes back up the same way it went down. This is the exact rhythm of every recursion: go down to the bottom, then come back up combining results.
Press Open one to peel a layer (the "going down" of recursion). When you hit the smallest solid doll — the base case — press Count back up to watch the totals combine on the way out.
A doll stack that never ends would be a nightmare — you would open forever and never count anything. The reason the doll demo terminated is that there was a smallest solid doll. That stopping point is the first of the only two ingredients you ever need for a working recursion.
Ingredient 1 — the base case. This is the smallest version of the problem, so small that you can answer it directly with no further recursion. It is the floor. It is where "going down" stops. For the dolls, the base case is the solid doll: "count = 1, and there is nothing inside." A recursion with no base case never stops calling itself — that is the bug that crashes the program, and we will see exactly how it crashes in Chapter 2.
Ingredient 2 — the recursive case. This handles every non-base situation by doing a tiny bit of work and then calling itself on a strictly smaller input — an input that is one step closer to the base case. The two crucial words are strictly smaller. If the call does not shrink the problem, you never reach the floor, and again you crash.
Before our even-only twist, let's nail the simplest classic. The factorial of n, written n!, is the product of all the integers from 1 to n. So 4! = 1 × 2 × 3 × 4 = 24. The self-similar observation that unlocks recursion is this: 4! is just 4 times 3!. And 3! is 3 times 2!. The big factorial contains a smaller factorial. That is the recursive case staring back at us.
Written as a recurrence — a rule that defines a value in terms of smaller values of itself — factorial is:
Now translate the recurrence line-for-line into code. Notice there is no loop, no accumulator, no counter — the structure of the function is the structure of the recurrence:
def factorial(n): if n <= 1: # BASE CASE — smallest problem, answered directly return 1 return n * factorial(n - 1) # RECURSIVE CASE — one step of work, then a smaller call
Three things are doing all the work, and they are exactly the two ingredients plus the "trust":
if n <= 1 guard is the base case. It must come first, before any recursive call, or the function would recurse even at the bottom.n - 1 is the shrink. Each call's input is strictly smaller, so we march toward the base case.n * in front is the combine step — the tiny bit of work this level contributes, applied to whatever the smaller call returns.This is the single most important skill in the whole lesson. We trace by hand, writing out each call as it descends, then resolving each return as we climb. We will use indentation to show depth — deeper indentation = deeper in the recursion.
Going down (each call cannot finish until its inner call answers, so it parks the multiplication and waits):
factorial(4) = 4 * factorial(3) # wait... factorial(3) = 3 * factorial(2) # wait... factorial(2) = 2 * factorial(1) # wait... factorial(1) = 1 # BASE CASE — no more waiting!
Coming back up (now the bottom answer is known, each parked multiplication unfreezes, deepest first):
factorial(1) = 1 factorial(2) = 2 * 1 = 2 factorial(3) = 3 * 2 = 6 factorial(4) = 4 * 6 = 24 # the final answer climbs all the way out
Read those two blocks together and you have seen the entire life of a recursion. Four calls go down. One base case answers. Four answers climb back up, each multiplying in its own number. The result, 24, equals 1×2×3×4 — exactly what factorial of 4 should be. We never wrote a loop. We never wrote an accumulator. We described one step and trusted the rest.
return n * factorial(n) (note: n, not n-1), the input never gets smaller, the base case is never reached, and the calls pile up forever until the program crashes. We will see that crash — the dreaded stack overflow — in Chapter 2. The fix is always one of: add a base case, or make the recursive call strictly smaller.Below, step through factorial by hand at your own pace. Each click adds the next call going down, then unwinds the returns coming up. Watch how the multiplications stay parked until the base case is hit.
Choose n, then press Step ↓ to descend one call and Step ↑ to resolve one return. The parked multiplications show what each level is waiting to finish.
In Chapter 1 we kept saying a call "parks its multiplication and waits." Where does that parked work physically live? It lives in a region of memory called the call stack. Understanding the stack turns recursion from magic into mechanism — and it is the single best cure for the "I can't keep all the levels in my head" panic.
Every time any function is called — recursive or not — the computer creates a small package of memory called a stack frame (or "activation record"). A frame holds everything that one specific call needs: the values of its arguments, its local variables, and a bookmark called the return address — the exact spot in the caller's code to jump back to when this call finishes.
These frames are stacked like a pile of cafeteria trays. You can only add to the top, and you can only remove from the top. That discipline has a name: LIFO — Last In, First Out. The most recently called function is always the first to finish and be removed. This is exactly why recursion unwinds deepest-first, just like we saw by hand.
So the two directions of recursion map perfectly onto two stack operations:
return removes the top frame and delivers its value to the frame now exposed beneath it. The stack shrinks.Let's freeze the stack at the deepest moment of factorial(4) — the instant factorial(1) is about to return. Four frames are stacked. Each remembers its own n and what it is waiting to multiply:
| Stack position | Frame | Local n | Parked work (waiting on) |
|---|---|---|---|
| top (deepest) | factorial(1) | 1 | nothing — base case, returns 1 now |
| ↑ | factorial(2) | 2 | 2 * (result of factorial(1)) |
| ↑ | factorial(3) | 3 | 3 * (result of factorial(2)) |
| bottom (first) | factorial(4) | 4 | 4 * (result of factorial(3)) |
This table is the answer to "where does the parked multiplication live?" Each frame stores its own n in its own private memory. The n=4 frame's variables are completely separate from the n=2 frame's — even though it is the same function. That isolation is why recursion works at all: every call gets its own fresh copy of the locals. This is also why the problem says "no globals": a recursive function carries its state in the frames, not in shared global variables.
The stack is not infinite. The operating system reserves a fixed chunk of memory for it — often around 1 MB — and each frame eats a slice. If recursion goes too deep (a missing or unreachable base case, or a genuinely enormous input), frames keep piling up until that chunk is exhausted. The program then crashes with a stack overflow. In Python you'll see RecursionError: maximum recursion depth exceeded, because Python sets a safety limit (about 1000 frames by default) and trips it deliberately before the real memory runs out.
# A recursion with NO base case — it never stops shrinking toward a floor def forever(n): return forever(n - 1) # shrinks, but there is no `if` to ever stop forever(5) # RecursionError: maximum recursion depth exceeded # The stack pushed ~1000 frames, found no base case, and gave up.
This is not a flaw in recursion; it is recursion honestly reporting that you forgot ingredient one. The cure is never "increase the limit" — it is "make sure the base case is reachable." Below, you can watch a stack grow and overflow. Crank n high and press play; the bars stack toward the ceiling, and when they hit it, you see the crash.
Each bar is a frame holding its own n. Play auto-runs the whole recursion: frames push upward (going down), then pop back (coming up). Lower the Stack limit below n to trigger a real stack overflow.
Now we earn the lesson. The AA174A question: write even_factorial(n) that returns the product of all even integers from 1 to n inclusive, with no loops and no globals. even_factorial(7) should give 2 × 4 × 6 = 48. Let us derive the recurrence rather than guess it — deriving is the difference between memorizing and understanding.
What is the largest even number we multiply when the input is 7? It is 6 (7 is odd, so we drop down to 6). When the input is 8? It is 8 itself. So the very first thing each call must do is find the largest even number not exceeding n. Call that step:
Now the self-similar insight. The product of all even numbers up to n is: step, multiplied by the product of all even numbers up to two below step. Why two below? Because even numbers come every other integer — the even number just before 6 is 4, not 5. So once we've used step, the rest of the problem is "even_factorial of step − 2." The big product literally contains a smaller even-product. There's our recursive case.
When do we stop? The problem tells us: the factorial of 0 and 1 are defined as 1. More generally, when there are no even numbers left to multiply — that is, when n drops to 1 or 0 (or below) — the product of an empty set of numbers is the multiplicative identity, 1. (Multiplying by 1 changes nothing, which is exactly why an empty product is 1, just as an empty sum is 0.)
Putting both ingredients together, the full recurrence is:
def even_factorial(n): if n <= 1: # BASE CASE: no even numbers left → empty product = 1 return 1 step = n if n % 2 == 0 else n - 1 # largest even ≤ n return step * even_factorial(step - 2) # this even × the smaller even-product
Read each line against the recurrence: the if n <= 1 is the base case; step = n if n % 2 == 0 else n - 1 computes the largest even number (n % 2 is the remainder when dividing by 2 — it's 0 for even numbers); and the final line is the recursive case, doing one multiplication and shrinking the problem by jumping to the next-lower even number. No loop. No accumulator. No global. Just the recurrence, transcribed.
step − 2 and not n − 1 or n − 2? Two reasons fused into one. First, we want only even numbers, and they're spaced 2 apart, so we descend by 2. Second, by basing the descent on step (the even number we just used) rather than on raw n, an odd input like 7 immediately snaps onto the even track: step = 6, next call is even_factorial(4). From then on every input is even, and we cleanly step 6 → 4 → 2 → 0 down to the base case.This is the trace the interviewer wants you to be able to do on a whiteboard. We follow the same down-then-up rhythm from Chapter 1, tracking step at each level.
Going down — each call computes its step, parks the multiplication, and calls a smaller copy:
even_factorial(7): n=7 is odd → step=6; return 6 * even_factorial(4) even_factorial(4): n=4 is even → step=4; return 4 * even_factorial(2) even_factorial(2): n=2 is even → step=2; return 2 * even_factorial(0) even_factorial(0): n=0 ≤ 1 → BASE CASE, return 1
Notice the inputs go 7 → 4 → 2 → 0. The odd 7 snapped to 4 (because step−2 = 6−2 = 4), and after that it's a clean even ladder down to the base case. Four frames are on the stack at the deepest point.
Coming back up — the base returns 1, then each parked multiplication unfreezes, deepest first:
even_factorial(0) = 1 even_factorial(2) = 2 * 1 = 2 even_factorial(4) = 4 * 2 = 8 even_factorial(7) = 6 * 8 = 48 # ✓ matches 2 × 4 × 6 = 48
And there it is: 48, climbing all the way out of the stack. Cross-check against the brute-force definition: the even numbers from 1 to 7 are 2, 4, 6, and 2 × 4 × 6 = 48. The recursion multiplied them in the reverse order (6 last, on the way out), but multiplication doesn't care about order, so we land on the same answer.
| Call | Even numbers in range | Expected | Recursion gives |
|---|---|---|---|
even_factorial(0) | none | 1 (empty product) | base case → 1 ✓ |
even_factorial(1) | none | 1 (empty product) | base case → 1 ✓ |
even_factorial(2) | 2 | 2 | 2 × ef(0) = 2 × 1 = 2 ✓ |
even_factorial(10) | 2,4,6,8,10 | 3840 | 10×8×6×4×2 = 3840 ✓ |
if n == 0: return 1. It looks fine — but feed it an odd n and watch it die. even_factorial(7) descends 7 → 4 → 2 → 0 and is saved only because it happens to land on 0. But even_factorial(1) would compute step = 0, then call even_factorial(−2), then even_factorial(−4)… it sails past 0 forever and stack-overflows. Always use n ≤ 1 (a "floor," catching everything at or below the boundary), never n == 0 (a single "trapdoor" that's easy to miss). Use ranges, not exact equality, for base cases.Below: hand-trace even_factorial for any n you choose, with the step shown at every level. Compare an odd n (watch the snap to the even ladder) against an even n.
Pick n. Step ↓ descends one call (showing how step is chosen); Step ↑ resolves one return. Try n = 7 to reproduce the 48 trace, then try an even n like 6.
even_factorial(7), what is the FIRST recursive call made (the input to the second frame)?You can now write recursion. The final question of any real engineer is: should you? Recursion is not always the right tool, and knowing the tradeoffs is what separates someone who memorized a pattern from someone who understands it.
Here is a fact that surprises most beginners: any recursion can be rewritten as a loop, and any loop can be rewritten as a recursion. They are equally powerful. The earlier loop version of even_factorial and the recursive version compute the exact same number. The difference is never what they can compute — it is how they manage state and how they read.
| Dimension | Recursion | Iteration (loop) |
|---|---|---|
| Where state lives | Implicitly, in stack frames (one per call) | Explicitly, in variables you declare |
| Memory used | O(depth) — grows with recursion depth | O(1) — constant, reuses the same variables |
| Risk | Stack overflow if too deep | None from depth; can infinite-loop if no exit |
| Reads best for | Self-similar / tree-shaped problems | Flat, sequential, "do this N times" problems |
Recursion shines when the problem itself branches or nests — when one problem naturally splits into several smaller copies. Walking a file system (each folder contains folders), parsing nested brackets or JSON, exploring a maze, and traversing a tree (a structure where each node has children) are all dramatically cleaner with recursion. Writing a loop for these forces you to manually rebuild a stack with your own list — you reinvent the call stack badly. Let the language's stack do it for you.
A classic example is the recursive sum-of-digits: how do you add up the digits of 1234? Peel off the last digit (4) and add it to the digit-sum of what remains (123). Same shape as factorial:
def digit_sum(n): if n < 10: # BASE CASE: a single digit is its own sum return n return (n % 10) + digit_sum(n // 10) # last digit + sum of the rest # digit_sum(1234) = 4 + digit_sum(123) = 4 + 3 + digit_sum(12) = ... = 4+3+2+1 = 10
For a plain "repeat N times" task — summing a list, counting to a million, marching through array indices — a loop is simpler, faster, and cannot overflow. Recursing a million levels deep to sum a list would crash with a stack overflow long before a loop would even break a sweat. The loop reuses one set of variables; the recursion would push a million frames. If the problem is flat and sequential, loop. If the problem nests or branches, recurse.
Recursion is the gateway to a huge fraction of computer science. Divide and conquer algorithms — merge sort, quicksort, binary search — are recursion: split the problem in half, solve each half, combine. Tree and graph traversal (depth-first search) is recursion. Dynamic programming starts as recursion and then caches repeated subproblems. Backtracking (solving Sudoku, N-Queens, regex matching) is recursion that undoes its choices on the way back up the stack. Master the base-case + shrink-toward-it + combine-on-the-way-up pattern here, and you have the skeleton key to all of them.
| Concept | What it is | Watch out for |
|---|---|---|
| Base case | Smallest input, answered with no recursion | Use a range (n ≤ 1), not exact equality (n == 0) |
| Recursive case | One step of work + a strictly smaller self-call | The call MUST shrink the input toward the base |
| Call stack | LIFO pile of frames; one frame per live call | Each frame holds its own locals — that's your state |
| Push / pop | Call pushes a frame; return pops it | Deepest call returns first (Last In, First Out) |
| Stack overflow | Too many frames; memory exhausted | Cause is almost always an unreachable base case |
| even_factorial | step × even_factorial(step−2), base n≤1→1 | step = largest even ≤ n |
even_factorial from scratch, and choose recursion vs iteration on purpose. That is genuine mastery of the foundation every advanced algorithm is built on.The widget in Chapter 2 pushed and popped frames when you clicked. Here, your recursion drives the stack. You implement the two lines that ARE the recurrence; the scaffold instruments every call so the heatmap below renders the live call stack — one row per depth, columns marching forward in time as frames push (going down) and pop (coming up). Press Run (Python boots once, ~5s), then scrub the animation.
The lesson taught you recursion four ways — story, stack, derivation, code. This workbook makes you create it. Every drill asks you to trace a call, write a base or recursive case, implement a variant, design a recurrence, or debug a broken one — never just recall. Work them with a blank sheet and a pencil; the checks verify your arithmetic, and every reveal walks the full path.
You cannot debug what you cannot trace. These drills make you walk a recursion down to its base case and back up, by hand.
factorial(n) with base if n <= 1: return 1, calling factorial(3) — which call is the FIRST to return a value without recursing further?When factorial(5) reaches its deepest point (just as factorial(1) is about to return), how many stack frames are alive at once?
The live frames are factorial(5), (4), (3), (2), (1) — one per value from 5 down to 1. That's 5 frames. The descent pushes a frame for each input, and none pop until the base case (n=1) returns.
Hand-trace factorial(4). What value does factorial(3) return on the way back up?
With digit_sum(n): base n<10 → n, else (n%10)+digit_sum(n//10). What does digit_sum(72) return?
factorial(4), while factorial(1) is running, what is the factorial(3) frame doing?Every recursion is a base case plus a shrinking recursive case. These make you produce each piece.
count_down(n) that prints n, n-1, …, 0, then stops, the best base case is:sum_to(n) = 1+2+…+n. Which recursive case is correct?Using sum_to(n) = n + sum_to(n-1), base n≤0 → 0, compute sum_to(4).
The headline problem and its relatives. Compute outputs by hand to prove your mental model matches the machine.
The headline. Product of even numbers up to 7.
Now an even input.
For even_factorial(9), what input does the FIRST recursive call use? (step = largest even ≤ 9, then step − 2.)
odd_factorial(n) (product of odd numbers up to n), how would you set step?Product of odd numbers from 1 to 7 (base n≤1 → 1).
power(b, e) = be via b * power(b, e-1). What's the base case?Using base e==0 → 1 and b * power(b, e-1), compute power(2, 5).
Euclid's algorithm: gcd(a,b) = gcd(b, a%b), base b==0 → a. Compute gcd(48, 36).
Recursive digit sum from Chapter 4.
The real skill: see a problem, find its self-similar core, and write the recurrence.
With fib(0)=0, fib(1)=1, and fib(n)=fib(n-1)+fib(n-2), compute fib(6).
length([]) = 0. The recursive case for a non-empty list is:How MANY even numbers are in 1..n? For n = 7, what does this count return? (It counts 2,4,6.)
Recurrence: count(n) = 1 + count(step-2) where step is the largest even ≤ n; base n≤1 → 0. Same skeleton as even_factorial but COMBINING with + instead of ×, and base 0 instead of 1.
Most recursion bugs are one of three things: missing base case, non-shrinking call, or wrong combine. Spot them.
def f(n): return n * f(n - 1) — runs forever. The bug is:def f(n):if n <= 1: return 1return n * f(n) — still overflows. Why?if n == 0: return 1 crashes on even_factorial(1). Why?def fac(n): return n + fac(n-1) if n > 1 else 1 — for n=4 it gives 10, not 24. The bug is:A buggy factorial uses base if n <= 0: return 1 but the recursive case n * factorial(n-1). What does it return for factorial(3)? (Trace it — the base now returns at n=0.)
Here it still gives the right 6, because multiplying by the n=1 term and then by base 1 changes nothing. The base n≤0 just adds one harmless extra frame. It's not a correctness bug for factorial — but it IS wasteful, and for even_factorial the analogous past-the-floor base would crash. Prefer the tightest correct base, n≤1.
RecursionError: maximum recursion depth exceeded. The correct first move is:Tie it together: stack reasoning, tradeoffs, and the big picture.
One more, bigger. Product of even numbers up to 12.