The Call Stack & Base Cases

Stage 3 begins: problems that recurse into themselves

Most of the course so far has been flat — a loop marches an index across an array, a pointer converges, a window slides. The Sorting module's merge sort and quicksort were the first exception: both called themselves recursively, and you used their recursion trees to derive their complexity. But that module treated recursion as a tool applied to sorting; it never explained the machine underneath the tool. Stage 3 is about data and problems that are defined in terms of smaller copies of themselves — a tree is a node plus two smaller trees; "all subsets of n items" is "all subsets of n−1 items, twice" — and this lesson makes that underlying machine concrete for the first time: the call stack. Recursion is not magic syntax; every recursive call you've already written ran on it. If you don't know exactly what that machine does on each call, you cannot reason about when it terminates, how much memory it costs, or why it crashes. This lesson makes the machine concrete first, then gives you the two tools — a base case and an induction argument — that let you prove a recursive function is correct instead of hoping it is.

Picture it like a stack of trays at a cafeteria counter. Every time a new task needs to happen before the current one can finish, you set the current tray down and start a fresh one on top of it — the tray underneath is still there, still holding everything you were in the middle of, just paused. You can only ever work on the top tray, and a tray only comes off the stack once whatever was on it is completely done. A recursive call is exactly this: pause what you're doing, start a smaller version of the same task on a fresh tray, and only pick your own tray back up once the one above it is cleared.

What a function call actually does in memory

Every time any function is called — recursive or not — the language runtime pushes a stack frame onto the call stack. A frame is a small block of memory holding three things:

1. The arguments and local variables for this invocation. Each call gets its own frame, so n inside factorial(3) and n inside factorial(2) are two different memory locations that happen to share a name.
2. The return address — where in the calling function to resume once this call finishes. This is how the program knows to come back.
3. A slot for the return value to be handed back to the caller.

Concretely, when factorial(3) calls factorial(1), the frame that gets pushed for that call holds: argument n = 1; a return address pointing at the return n * factorial(n - 1) line inside factorial(2)'s own frame (so execution knows exactly where to resume once factorial(1) is done); and, once the base case fires, a return value of 1 waiting to be handed back to that resume point.

When a function returns, its frame is popped — the memory is reclaimed, and control jumps to the saved return address. The stack is a literal LIFO stack (Module 8): the most recently called function is the first to finish and return. Recursion is not a special language feature; it is just the ordinary call mechanism pointed at the same function, so that many frames for the same function are on the stack at once, each frozen mid-execution, waiting for the one above it to return.

Making it concrete: factorial

factorial(n) = n × factorial(n − 1), with factorial(0) = 1. Watch the frames build up and then unwind:

def factorial(n: int) -> int:
    if n == 0:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: shrink toward the base

Trace factorial(3). The stack grows on the way down — each call suspends itself mid-expression, unable to compute n * ... until the inner call returns, so its frame stays on the stack:

Two separate phases fall out of this picture, and naming them pays off for the rest of Stage 3. The winding phase (calls pushing, going deeper) is where you do work before recursing; the unwinding phase (frames popping, returning back up) is where you do work with the results of deeper calls. In factorial, the multiplication n * ... happens on the way back up — during unwinding. The maximum stack depth here is 4 frames (n = 3 down to n = 0), and in general n + 1 frames. Hold onto that number: it is not free, and it is the whole subject of the "Recursion vs. Iteration" lesson.

The base case is what makes recursion terminate

A recursive function needs two parts, and both are load-bearing:

• The recursive case must call the function on a strictly smaller subproblem — n − 1, half the array, one child node. "Makes progress toward the base" is the exact requirement.
• The base case is the smallest subproblem, solved directly with no further recursion. It is the floor the descent stops at.

Remove or mis-write the base case and the descent never stops. But be precise about how it fails — this is a common misconception:

A recursion with a broken base case does not hang like an infinite while loop. It crashes with a stack overflow.

The difference is memory. An infinite loop reuses one frame forever and consumes no additional memory — it just spins. Infinite recursion pushes a new frame on every call and never pops any of them, so the stack grows without bound until it hits the runtime's stack-size limit (a few thousand to a few tens of thousands of frames, depending on language and settings) and the program is killed. Watch what "wrong base case," not just "missing," looks like:

def broken(n: int) -> int:
    if n == 0:
        return 1
    return n * broken(n - 2)   # BUG: from odd n, we go 3 → 1 → -1 → -3 → ...
                               # and never hit exactly 0

broken(4) is fine (4 → 2 → 0). broken(3) steps 3 → 1 → −1 → −3 → …, sailing past 0 forever: RecursionError in Python, RangeError: Maximum call stack size exceeded in JavaScript. The lesson is that "has a base case" is not enough — every recursive path must provably reach a base case. The fix is a base case that catches the whole descent, e.g. if n <= 0: return 1.

Proving a recursive function correct: induction

Here is the part that separates using recursion from trusting it. You never trace a recursive call all the way to the bottom in your head — that defeats the purpose and is infeasible for real inputs. Instead you prove correctness the same way mathematicians prove statements about all integers: induction, which maps onto recursion's two parts exactly.

1. Base case. Show the function returns the right answer for the smallest input(s). For factorial, factorial(0) returns 1, and 0! = 1. ✓
2. Inductive step. Assume the recursive call is already correct on every smaller input (this is the inductive hypothesis), then show this one call combines those correct sub-answers into the correct answer. For factorial(n) with n > 0: assume factorial(n − 1) correctly returns (n−1)!. Then n * factorial(n − 1) = n × (n−1)! = n!. ✓

That's a complete proof, and notice what it did not require: you never unfolded the recursion. You reasoned about one level — assuming the level below is right — and the induction principle guarantees it holds all the way down, because the recursion is guaranteed to reach the base case (which is why the termination argument above is not optional; induction is only valid if the descent bottoms out). This "assume the smaller calls already work" move is the single most important habit in Stage 3. When you write the backtracking solutions later, you will design them by trusting the recursive call does its job on the smaller subproblem, not by simulating the whole tree in your head.

A preview of why Module 24 exists: naive Fibonacci

One more example, because it foreshadows a whole later module. Fibonacci is doubly recursive — each call spawns two smaller calls:

def fib(n: int) -> int:
    if n < 2:            # base cases: fib(0) = 0, fib(1) = 1
        return n
    return fib(n - 1) + fib(n - 2)

This is correct by the same induction argument (base cases right; the step adds two correct smaller answers). But it is disastrously slow. The call tree branches two ways at every level, so its size roughly doubles each level down — computing fib(n) makes on the order of 2ⁿ calls, an exponential number. (More precisely, the count grows as Θ(φⁿ) where φ ≈ 1.618 is the golden ratio — strictly slower-growing than 2ⁿ, since not every branch survives to full depth, but still exponential; "O(2ⁿ)" is the loose, easy-to-state upper bound this course uses, and it's the one you should reach for in an interview.) The reason is pure redundancy: fib(5) calls fib(4) and fib(3); fib(4) also calls fib(3); that entire fib(3) subtree is recomputed from scratch every time it appears. Counting calls directly on fib(5) makes this concrete: fib(3) runs twice, fib(2) runs three times, fib(1) runs five times, fib(0) runs three times — 15 calls total to compute one value that a single pass of the iterative version would reach in 5 steps. The same subproblems are re-solved an exponential number of times.

Nothing is wrong with the recursion logically — it is wrong economically. The fix is to remember each subproblem's answer the first time you compute it, so the exponential tree collapses to a linear number of distinct subproblems. That fix is called memoization / dynamic programming, and it is the entire subject of Module 24. For now, the takeaway is the diagnostic skill: a recursion whose subproblems overlap (the same input recurs across different branches) is a red flag for exponential blowup, and recognizing it early is what tells you "this needs DP" later.

Note the last row carefully, because it is a distinction people routinely get wrong: fib's time is exponential but its space is only linear. Time counts every node the recursion ever visits; stack space counts only the frames alive at one instant, which is the current root-to-leaf depth — the tree is walked one path at a time, depth-first, popping each branch before starting the next. This time-vs-depth gap comes back in every backtracking analysis in this module.