Python Recursion

A function is recursive when it calls itself. Recursion solves a problem by reducing it to a smaller version of the same problem, until the problem is so small that the answer is obvious. That smallest case is called the base case, and every recursive function needs one, or it would call itself forever.

Factorial

The factorial of n, written n!, is n × (n − 1) × … × 1. It can be defined in terms of itself: n! = n × (n − 1)!, and 1! = 1. The Python version follows the definition exactly:

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

for n in [1, 3, 5, 10]:
    print(f"{n}! = {factorial(n)}")

1! = 1
3! = 6
5! = 120
10! = 3628800

When factorial(3) runs, it calls factorial(2), which calls factorial(1). That call returns 1 straight away, and the answers come back up: 2 × 1 = 2, then 3 × 2 = 6.

Recursion on nested data

Recursion shines when data contains smaller pieces of the same shape, such as folders inside folders or lists inside lists:

def deep_sum(items):
    total = 0
    for x in items:
        if isinstance(x, list):
            total += deep_sum(x)      # the same problem, smaller
        else:
            total += x
    return total

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

28

A loop alone cannot easily follow an unknown depth of nesting, but the recursive function handles any depth.

The recursion limit

Each call waits for the call it made, and Python keeps them all in memory. To protect itself, Python allows only about a thousand calls in a chain; going deeper raises a RecursionError. This usually means the base case is missing or never reached, as in a factorial function that forgets the if.

Faster recursion with a cache

The Fibonacci numbers are defined by fib(n) = fib(n − 1) + fib(n − 2). The plain recursive version recomputes the same values again and again, and becomes very slow for large n. The functools.cache decorator remembers results that were already computed:

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print([fib(n) for n in range(10)])
print(fib(80))

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
23416728348467685

Many recursive functions can also be written as loops, which are often faster and never hit the limit. Choose recursion when it makes the solution clearer.

Practice exercises

1. Write a recursive function that returns the sum of the numbers from 1 to n.
2. Write a recursive function that counts down from n to 1, printing each number.
3. Write a recursive function that reverses a string.
4. Remove the base case from factorial, run it, and read the RecursionError and its hint.