Recursion

The shape

A recursive function calls itself on a smaller version of the problem, and has a base case that does not recurse:

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

countdown(3)

3
2
1
liftoff

Every recursive function needs two things:

• a base case that returns without calling itself
• a recursive step that moves towards that base case

Miss either and it never stops.

Factorial

The textbook example, because the maths is already recursive:

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

print(factorial(5))

120

factorial(5) waits for factorial(4), which waits for factorial(3), and so on down to the base case. Then the answers multiply back up the chain.

Python has a recursion limit

Each call takes a frame on the stack, and Python caps how deep that can go:

import sys
print(sys.getrecursionlimit())

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

try:
    deep(0)
except RecursionError:
    print("RecursionError, as expected")

1000
RecursionError, as expected

Python does not optimise tail calls, so a recursion that would be a loop in another language will hit this limit here. When the depth is proportional to your input size, write the loop.

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

print(factorial(5))

120

Where recursion earns its place

Not counting down — that is a loop. Recursion shines on data that is itself nested, where the depth is small and unknown:

def total(items):
    running = 0
    for item in items:
        if isinstance(item, list):
            running += total(item)
        else:
            running += item
    return running

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

21

Writing that with a loop means managing your own stack of pending lists. The recursive version is the shape of the data.

Walking a nested dictionary is the same idea, and is how you would flatten JSON:

def leaves(data):
    found = []
    for value in data.values():
        if isinstance(value, dict):
            found.extend(leaves(value))
        else:
            found.append(value)
    return found

tree = {"a": 1, "b": {"c": 2, "d": {"e": 3}}}
print(leaves(tree))

[1, 2, 3]

Repeated work

Naive recursion can redo the same call enormously often. Fibonacci is the standard demonstration:

calls = 0

def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(20), "computed with", calls, "calls")

6765 computed with 21891 calls

Caching the results fixes it completely:

from functools import lru_cache

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

print(fib(20))
print(fib.cache_info().currsize)

6765
21

Twenty-one cached results instead of twenty-two thousand calls.