The call stack

When a function calls another function, the first one must wait and later carry on where it stopped. Python keeps track of all the waiting calls on the call stack. Recursion is just many calls to the same function on that stack.

Frames

Each call gets a frame: a small record that holds the call’s own local names (its parameters and variables) and the place in the code where it is. You met frames in PYTH-3. When a function calls another, Python puts a new frame on top. When a call returns, its frame is removed and the frame below carries on. This is a stack: the last frame added is the first one removed.

So each recursive call has its own n. The n in fact(3) and the n in fact(2) are different names in different frames, even though the code is the same.

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

print(fact(4))

Work on the way down, work on the way up

Code before the recursive call runs on the way down, from the first call to the base case. Code after it runs on the way back up, in reverse order. Compare:

def down(n):
    if n == 0:
        return
    print(n)        # before the call: prints 3, 2, 1
    down(n - 1)

def up(n):
    if n == 0:
        return
    up(n - 1)
    print(n)        # after the call: prints 1, 2, 3

In fact, the multiplication happens on the way up. Each frame waits for the answer from below, then multiplies by its own n.

Depth is space

The largest number of frames on the stack at once is the depth of the recursion. Each frame uses memory, so the depth is extra space (BIGO-4):

• fact(n) goes n deep: O(n) extra space.
• power(x, n) from lesson 1 goes about log₂ n deep: O(log n).
• A function that makes two calls, one after the other, is only as deep as its longest chain of calls, not as deep as its number of calls. The first call finishes and its frames are gone before the second starts.

Why Python does not remove the last call

In return f(n - 1), the call is the last thing the function does. Some languages then reuse the frame, so this kind of recursion uses no extra space. Python does not do this, on purpose, so that error messages show every call. In Python, write such a function as a loop.

Now try RECR-P1, Power on a clock: its recursion is only about 60 frames deep, even for n = 10¹⁸ (a 1 followed by 18 zeros).