Recursion

A recursive function solves a problem by calling itself on a smaller version of the same problem. It's a natural fit for data that's nested inside itself — folders within folders, comments with replies, JSON objects within objects — and for "divide and conquer" algorithms.

The two parts of every recursive function

PY factorial.py

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

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

Output

120
2432902008176640000

Base case — a simple input answered directly, without recursion (n <= 1). Without it, the function would call itself forever.
Recursive case — reduce the problem and call the function on the smaller piece (factorial(n - 1)), then combine the result.

So factorial(5) is 5 * factorial(4), which is 5 * 4 * factorial(3), and so on until the base case returns 1 and the multiplications unwind.

Tracing the calls

PY trace.py

def countdown(n, depth=0):
    indent = "  " * depth
    if n == 0:
        print(indent + "liftoff!")
        return
    print(f"{indent}countdown({n})")
    countdown(n - 1, depth + 1)
    print(f"{indent}back in countdown({n})")

countdown(3)

Output

countdown(3)
  countdown(2)
    countdown(1)
      liftoff!
    back in countdown(1)
  back in countdown(2)
back in countdown(3)

Each call waits for the one it started to finish. The waiting calls are kept on the call stack.

Recursion on nested data

Recursion really pays off when the data's depth isn't known in advance:

PY nested.py

def flatten(items):
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

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

def total_size(folder):
    size = sum(folder.get("files", {}).values())
    for sub in folder.get("folders", []):
        size += total_size(sub)
    return size

project = {
    "files": {"README.md": 2},
    "folders": [
        {"files": {"app.py": 12, "util.py": 4}},
        {"files": {}, "folders": [{"files": {"logo.png": 40}}]},
    ],
}
print(total_size(project), "KB")

Output

[1, 2, 3, 4, 5, 6, 7, 8]
58 KB

Divide and conquer

Many efficient algorithms split a problem in half recursively. Binary search finds an item in a sorted list in very few steps:

PY binary_search.py

def binary_search(items, target, low=0, high=None):
    if high is None:
        high = len(items) - 1
    if low > high:
        return -1
    mid = (low + high) // 2
    if items[mid] == target:
        return mid
    if items[mid] < target:
        return binary_search(items, target, mid + 1, high)
    return binary_search(items, target, low, mid - 1)

data = list(range(0, 1000, 3))
print(binary_search(data, 501), binary_search(data, 500))

Output

167 -1

The recursion limit

Python limits how deep recursion can go (usually 1000 calls) to protect against infinite recursion:

PY limit.py

import sys

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

try:
    depth(0)
except RecursionError as err:
    print("RecursionError:", err)

print(sys.getrecursionlimit())

Output

RecursionError: maximum recursion depth exceeded
1000

Python doesn't optimise "tail calls" the way some languages do, so very deep recursion (like counting to a million) should be written as a loop instead.

Avoiding repeated work with caching

The naive recursive Fibonacci function recalculates the same values over and over, which becomes painfully slow. Caching results fixes it:

PY fibonacci.py

from functools import cache

calls = 0

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

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

print(fib_slow(20), "took", calls, "calls")
print(fib(100))

Output

6765 took 21891 calls
354224848179261915075

@cache is a decorator (lesson 34) that remembers each result, turning an exponential algorithm into a linear one.

Recursion or a loop?

Use recursion when the problem is naturally recursive — trees, nested structures, divide-and-conquer — and the depth stays modest. Use a loop for simple repetition, where it's clearer and has no depth limit.

Try it yourself

PreviousLambdas & Higher-Order NextType Hints