Recursion

A function that calls itself

Predict what this prints.

def countdown(n):
    if n == 0:
        print("Go!")
        return
    print(n)
    countdown(n - 1)

countdown(3)

3
2
1
Go!

A function calling itself is recursionrecursionA function that calls itself, each time on a smaller version of the problem, until it reaches a case it can answer directly.. It needs two parts. The base casebase caseThe case a recursive function answers directly, without calling itself. It's what stops the recursion. answers without calling again: here, n == 0. The recursive caserecursive caseThe part of a recursive function that calls itself on a smaller problem, like countdown(n - 1). calls the function on a smaller problem, n - 1, so every call gets closer to the base case. A bare return ends the call without a value (it returns None).

Each call has its own n

The factorial of 3, written 3!, is 3 × 2 × 1 = 6. Notice that 3! is 3 × 2!, 2! is 2 × 1!, and 1! is just 1. That's a recursive definition, and it turns straight into code. Base case first:

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

print(fact(3))
print(fact(5))

fact(3) can't finish until it knows fact(2), which waits for fact(1). Step through it, slowly; this diagram is the whole lesson. When line 4 runs fact(n - 1), a new frame appears below the one whose line it is, with its own n. When a call reaches a return, the tab under its frame shows the value going back up.

At step 6 there are three different ns alive at once, one in each frame, and none of them ever changes. If you pictured a loop, you pictured one n going 3, 2, 1. The frames pile up on the way down; that pile is the call stackcall stackThe frames of every call that hasn't finished yet, newest last. Each call's frame goes when it returns..

On the way back, each frame hands its value to the frame that called it, and that frame finishes its own line with its own n. fact(1) returns 1 to fact(2). fact(2)'s n is still 2, so it works out 2 × 1 and returns 2 to fact(3). fact(3)'s n is still 3, so it works out 3 × 2 and returns 6, which r gets. Python's error messages list the call stack too, oldest call first, which is why they say "most recent call last".

The way back

A loop runs its lines once per round and moves on. A recursive call comes back. Predict:

def show(n):
    if n == 0:
        return
    print("before", n)
    show(n - 1)
    print("after", n)

show(2)

before 2
before 1
after 1
after 2

Every call finishes its own lines after the call inside it returns, and the innermost call finishes first. If you pictured a loop, you expected after 2 right after before 2.

Without a base case, the calls never stop. Python allows only so many frames on the stack, then stops the program:

When to use recursion

Honestly, for counting down or multiplying, a loop is simpler and faster. Recursion is here because it shines on data that has the same shape inside itself: folders in folders, a family tree, a list of lists of lists. You'll meet it again in data structures, algorithms, and job interviews. Here's a total that works however deep the lists go:

def total(items):
    result = 0
    for item in items:
        if type(item) == list:
            result = result + total(item)
        else:
            result = result + item
    return result

print(total([1, [2, 3], [4, [5]]]))

Each plain number is simply added. A list inside the list makes total call itself on that smaller list, and a list with no lists inside is the base case: the loop just adds its numbers. A loop alone couldn't know in advance how many levels to go down.