Recursion

A recursive function is one that calls itself. It solves a problem by breaking it into a smaller version of the same problem.

Countdown

def countdown(n):
    if n == 0:              # base case: stop here
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)        # recursive case: a smaller problem

countdown(5)

Every recursive function needs two parts:

1. A base case that stops the recursion.
2. A recursive case that moves towards the base case.

Factorial

The factorial of n (written n!) is n × (n−1) × ... × 1. Notice that 5! = 5 × 4!, which is a smaller version of the same problem:

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

print(factorial(5))
print(factorial(20))

Here is how factorial(4) unfolds:

factorial(4) = 4 * factorial(3)
             = 4 * 3 * factorial(2)
             = 4 * 3 * 2 * factorial(1)
             = 4 * 3 * 2 * 1
             = 24

Where recursion is natural: nested data

Recursion fits data that contains smaller copies of itself, such as folders inside folders or lists inside lists:

def total(items):
    result = 0
    for item in items:
        if isinstance(item, list):
            result += total(item)     # a list inside: recurse
        else:
            result += item
    return result

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

Writing that with loops alone is surprisingly awkward.

Forgetting the base case

Without a base case, the function calls itself forever, until Python stops it:

def forever(n):
    return forever(n + 1)

forever(1)

RecursionError: maximum recursion depth exceeded. Python limits recursion to about 1,000 levels deep to protect your program.