Recursion & the Call Stack

A function that calls itself sounds like a riddle or a bug. It's neither. Recursion is one of the cleanest ways to solve a problem that contains smaller copies of itself, and once you can see the call stack grow and collapse, the magic turns into bookkeeping you can predict.

The classic example: to compute factorial(4) you need factorial(3), which needs factorial(2), which needs factorial(1). The problem is the same shape at every step, just smaller. That's the signal that recursion fits.

Two parts, always

Every correct recursive function has exactly two pieces, and missing either one breaks it.

• The base case is the smallest version of the problem, the one you can answer outright, with no further recursion. For factorial, factorial(1) is just 1. It's the floor the recursion lands on.
• The recursive case solves the current problem in terms of a smaller one, trusting the function to handle that smaller piece. factorial(n) is n * factorial(n - 1).

The recursive case has to march toward the base case, or it never stops. factorial(n - 1) shrinks n by one each call, so it's guaranteed to hit factorial(1) eventually. Leave out the base case (or write a recursive case that doesn't get closer to it) and the function calls itself forever, until the language gives up and crashes. In Python that's a RecursionError: maximum recursion depth exceeded, which is the runtime saving you from an infinite loop. Don't go run one to see it. Just know that's the failure mode of a missing base case.

The call stack: a stack of paused work

Here's what's actually happening underneath. When a function calls another function, the current one pauses and the computer records where to come back. With recursion, the function pauses itself, over and over, and each paused call piles up on the call stack.

Step through factorial(4) and watch the stack grow on the way down (each call waiting on the one below it), hit the base case, then unwind as each paused call gets its answer and multiplies:

Read it as two phases. On the way down, calls stack up: factorial(4) can't finish until factorial(3) returns, which can't finish until factorial(2) returns, and so on. Nothing is computed yet. They're all parked, waiting. The moment factorial(1) hits the base case and returns 1, the unwinding starts: 2 * 1 = 2 returns, then 3 * 2 = 6, then 4 * 6 = 24, each paused call waking up, doing its one multiplication, and handing the result up to whoever was waiting on it.

That stack of parked calls is real memory. Recurse a million levels deep and you'll exhaust it, which is exactly why Python caps recursion depth instead of letting your program eat all the RAM.

Writing it yourself

Here's factorial and a recursive list-sum, both built from the same two-part recipe. Run it, then bump the numbers or swap the list:

sum_list follows the identical pattern: the empty list is the base case (sum is 0), and every other list is "the first number plus the sum of everything after it." Each call hands a shorter list to the next, marching toward empty. Same two parts, different problem.

If you're rusty on how a function returns a value to its caller in the first place, the Python functions lesson is the foundation this whole idea sits on. Recursion is just a function whose caller happens to be itself. The broader Python series walks the basics if you want them in order.

Where this leaves you

Recursion is two parts (a base case that stops, and a recursive case that shrinks the problem toward it) running on a call stack that grows as calls pile up and unwinds as they return. Get those two parts right and the stack takes care of itself.

It's also the engine behind some of the fastest algorithms there are. Before we get there, though, we start with the slow-but-simple sorts everyone learns first. Next: Sorting I: Bubble, Selection & Insertion.