Recursion: watch the call stack

Some problems contain smaller copies of themselves. The factorial of 4 is 4 × 3 × 2 × 1, which is just 4 times the factorial of 3. So a function can answer "what is factorial(4)?" by asking itself "what is factorial(3)?", and so on down, until the question is small enough to answer outright.

That raises a fair question: if factorial is still running when it calls factorial again, where does the first call keep its n while the second one runs? The answer is the call stack, and once you can see it, recursion stops feeling like magic.

base case

An input small enough to answer directly, without calling again. Every recursion needs one, or it never stops.

recursive case

An input answered by calling the same function on a smaller input, then using its answer.

frame

The memory for one call: its parameters and local variables, and where it is in the code.

call stack

The frames of every call that hasn't returned yet. A new call adds a frame on top; a return removes it.

Run it, then step through. On the left is the call stack: the global frame, then one frame per call that is still running. Each factorial frame has its own n. The calls pile up until factorial(1) hits the base case; then each frame returns its answer to the one below and disappears.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

result = factorial(4)
print(result)

This function adds up a list by taking the first item and adding the total of the rest. Each call passes the list on with a bigger i.

def total(nums, i):
    if i == len(nums):
        return 0
    return nums[i] + total(nums, i + 1)

values = [3, 1, 4]
print(total(values, 0))

When a function calls itself more than once, as Fibonacci does, the stack goes up and down many times. Drawing every call as a node, joined to the call that made it, gives the call tree. At any moment, the call stack is the path from the top call down to the call that is running.

• A recursive function answers a big input by calling itself on a smaller one, and needs a base case to stop.
• Every call gets its own frame, so the caller's variables are safe while it waits.
• The call stack holds the calls still running: the newest on top, returning first.
• Passing a list passes a reference: every frame sees the same list.
• Next: memoization, for recursion that asks the same question twice, and backtracking, for recursion that makes a choice, explores it and undoes it.