Recursion

Think of a matryoshka, a Russian nesting doll. You open the big doll, and inside is the same doll, only smaller. You open that one, and inside is a smaller one still. This goes on until you reach the smallest doll: it is solid and does not open.

Some problems work the same way: a big problem can be reduced to the same problem, only smaller. The factorial of a number n is the product of all integers from 1 to n. For example, the factorial of 4 is 1 * 2 * 3 * 4, that is, 24.

It is defined by two rules:

• the factorial of 0 is 1;
• the factorial of n is n times the factorial of n - 1.

A Python function repeats this definition word for word by calling itself:

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


print(factorial(4))  # 24
print(factorial(0))  # 1

Let's see how it computes factorial(4), through the eyes of the matryoshka:

1. factorial(4) does not know the answer at once and opens a smaller doll: it calls factorial(3).
2. factorial(3) likewise calls factorial(2), which calls factorial(1), which calls factorial(0).
3. factorial(0) is the smallest doll: it returns 1 at once.
4. Then the dolls close in reverse order, and each call finishes its own multiplication.

The two branches of a recursive function

Recursion is a function calling itself. A recursive function always has two branches. Let's look at each.

The base case

The branch in which the function returns a result without recursing is called the base case. In factorial it is if n == 0: return 1. It is the smallest matryoshka: it does not open.

Without a base case, the calls would never end. It must be reachable: every step of the recursion has to bring the argument closer to it.

The recursive step

The line return n * factorial(n - 1) calls the same function with an argument one smaller. The call factorial(4) waits for the result of factorial(3), which waits for factorial(2), and so on down to factorial(0).

Then the results travel back up the chain: 1, 1, 2, 6 and, finally, 24.

The call stack

Each call has its own parameter n, like any local variable. So the calls do not interfere with each other. While a call waits, Python keeps its variables and the place to return the result to in a separate record, a frame.

Unfinished frames pile up in the call stack. It is like a stack of plates:

• a new call puts a plate on top;
• a finished call takes the top plate off.

The bottom plate is <module>: that is what Python calls the code written in the file outside any function. Press "Next step" and watch the stack grow up to factorial(0) and then come apart from the top down. The widget computes factorial(3) so that the stack fits on the screen.

Each box in the widget is a frame. Notice two things. Each frame has its own n, and the values never mix. And the results come back in reverse order: the call that started last finishes first.

This is where the matryoshka picture stops working. Real dolls would take five of them, while the program has one function. Only each call's data is kept separately.

How the result is built

Each call waits for the deeper call to return, and only then finishes its own expression. The order of the parts in the result is set by the expression after return itself. This function puts its digit after the result of the next call:

def digits_up(n):
    if n == 0:
        return ""
    return digits_up(n - 1) + str(n)


print(digits_up(3))  # 123

Let's see how the string is built:

1. digits_up(0) returns an empty string, and the digit 0 does not get into the result.
2. digits_up(1) gives "" + "1".
3. digits_up(2) gives "1" + "2".
4. digits_up(3) gives "12" + "3", that is, "123".

If you put str(n) before the call, the digits come out in reverse order: "321".

Recursion depth

Until a call has finished, its frame stays on the stack. So the number of nested calls is limited: after about 1000, the program stops with a RecursionError.

Some languages turn a recursive call that is the function's last action into a loop, and the stack does not grow. This is called tail call optimization. Interviewers like to ask: "Does Python have it?" The answer:

• no, Python does not do it;
• every nested call, even one in a return line, takes its own frame;
• when there can be more than a thousand nested calls, a loop is written instead of recursion.

The same factorial as a loop:

def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result = result * i
    return result


print(factorial_loop(4))  # 24

The loop calls no new functions: the variables result and i change within one frame. However many steps there are, the stack of plates does not grow.

Common mistake

A recursive function is called with an argument from which the base case cannot be reached:

print(factorial(-1))  # ✗

RecursionError: maximum recursion depth exceeded

From -1 the chain goes to -2, -3 and further, and the condition n == 0 never holds. The frames pile up until they hit the limit. Check that the base case can be reached from every valid argument. Reject invalid arguments before the recursion: for example, return None at once when n < 0.

Key points

• A recursive function calls itself, and it needs a reachable base case.
• Each call has its own frame with its own variables; the frames pile up in the call stack.
• The results come back in reverse order: the deepest call finishes first.
• Python does not do tail call optimization, and after about 1000 nested calls a RecursionError is raised.