Recursion

The idea

Some problems contain a smaller copy of themselves. The sum of a list is the first number plus the sum of the rest of the list. The size of a folder is the size of its files plus the sizes of its subfolders. Recursion uses exactly that shape: a function that solves a problem by calling itself on the smaller copy, trusting that call to return the right answer.

A classic example is the factorial of a whole number n, written n!: the product 1 × 2 × … × n, with 0! defined as 1. Since 5! = 5 × 4!, and 4! = 4 × 3!, the definition can refer to itself:

FUNCTION factorial(n)
    IF n = 0 THEN
        RETURN 1
    ELSE
        RETURN n × factorial(n − 1)
    END IF
END FUNCTION

This is not circular reasoning, because every call works on a smaller number, and the chain stops at 0. For Python's syntax and a first example, see Functions in the Python topic.

Base case and recursive case

Every correct recursive function has two parts.

• A base case: an input so simple that the function answers it directly, without calling itself. For the factorial, that is n = 0. For a list, it is usually the empty list.
• A recursive case: the function reduces the problem to a smaller one, calls itself on that, and combines the result with a little work of its own.

Both are needed. Without a base case, the calls never stop. Without progress toward the base case — for example factorial(n) calling factorial(n) again, or factorial(-1), which counts down past 0 forever — they never stop either.

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


def total(numbers):
    if not numbers:                  # base case: an empty list sums to 0
        return 0
    return numbers[0] + total(numbers[1:])   # first item + sum of the rest


print(factorial(5))
print(total([4.50, 2.25, 3.00]))

120
9.75

Tracing recursive calls

To see what really happens, let the function report each call and each return. The indentation shows how deep the calls are nested.

def factorial(n, depth=0):
    indent = "  " * depth
    print(f"{indent}factorial({n}) called")
    if n == 0:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)
    print(f"{indent}factorial({n}) returns {result}")
    return result


factorial(3)

factorial(3) called
  factorial(2) called
    factorial(1) called
      factorial(0) called
      factorial(0) returns 1
    factorial(1) returns 1
  factorial(2) returns 2
factorial(3) returns 6

The calls go down first, each one waiting for the next. Only when factorial(0) reaches the base case does anything return, and then the waiting calls finish in reverse order: 1 × 1, 2 × 1, 3 × 2.

The call stack

A waiting call has to remember where it was: its parameters, its local variables and the point to continue from. The program keeps this information in a call stack: each function call pushes a new frame on top, and each return removes the top frame. Only the top frame is running; the frames below it are paused. This is true for every function call, not only recursive ones — recursion just makes the stack tall.

Stack overflow

The call stack has a limited size. A recursion that goes too deep — because the base case is missing, is never reached, or the input is simply very large — runs out of room. This is a stack overflow. In C, it usually crashes the program outright. Python protects itself with a recursion limit: in CPython, the standard interpreter, the default is 1000 nested calls, and going deeper raises a RecursionError.

import sys


def count_down(n):
    if n == 0:
        return "Liftoff!"
    return count_down(n - 1)


print(sys.getrecursionlimit())
print(count_down(500))       # 501 nested calls: fine
print(count_down(5000))      # 5001 nested calls: too deep

1000
Liftoff!
RecursionError: maximum recursion depth exceeded

The function above is correct — it has a base case and reaches it. It fails only because the input is too large for recursion in Python. sys.setrecursionlimit() can raise the limit, but the real stack of the interpreter is still finite, so the better fix for deep, linear recursion is a loop.

Recursion and iteration

Any recursive function can be rewritten with a loop, and the other way around. For a linear recursion such as factorial, the loop version keeps its progress in a few variables instead of stack frames, so it uses a fixed amount of memory and has no depth limit.

def factorial_recursive(n):
    if n == 0:
        return 1
    return n * factorial_recursive(n - 1)


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


for n in [0, 1, 5, 10]:
    print(n, factorial_recursive(n), factorial_iterative(n))

# 5000 would overflow the recursive version; the loop has no problem.
print(factorial_iterative(5000).bit_length(), "bits")

0 1 1
1 1 1
5 120 120
10 3628800 3628800
54233 bits

So why use recursion at all? Because for some problems the recursive version is much shorter and clearer, and matches how the problem is defined. The loop version of a function that walks a tree must keep its own stack of "places still to visit" — work that recursion gets for free from the call stack.

Tree-shaped recursion

A function that calls itself more than once per call produces a tree of calls instead of a chain. The Fibonacci numbers are the standard example: each number is the sum of the two before it (0, 1, 1, 2, 3, 5, 8, …), which translates directly into code.

calls = 0


def fib(n):
    global calls
    calls += 1
    if n < 2:                        # base cases: fib(0) = 0, fib(1) = 1
        return n
    return fib(n - 1) + fib(n - 2)   # two recursive calls


for n in [10, 20, 25]:
    calls = 0
    result = fib(n)
    print(f"fib({n}) = {result} after {calls} calls")

fib(10) = 55 after 177 calls
fib(20) = 6765 after 21891 calls
fib(25) = 75025 after 242785 calls

The code is correct, but the number of calls explodes: adding 5 to n multiplies the work by about 11. The reason is that the same values are computed again and again. Already in fib(4), fib(2) is computed twice:

Memoization

The fix is to remember answers. Memoization stores the result of each call in a lookup table the first time it is computed; later calls with the same argument return the stored result immediately. The tree collapses into a chain, and each fib(k) is computed only once.

calls = 0
known = {0: 0, 1: 1}                 # the base cases, already "remembered"


def fib(n):
    global calls
    calls += 1
    if n not in known:
        known[n] = fib(n - 1) + fib(n - 2)
    return known[n]


print(fib(25), "after", calls, "calls")
print(fib(90), "after", calls, "calls in total")

75025 after 49 calls
2880067194370816120 after 180 calls in total

In Python you rarely write the table yourself: the decorator @functools.cache (or @functools.lru_cache, which can limit the table's size) adds memoization to any function whose arguments are hashable. Memoization only makes sense for functions that always return the same result for the same arguments.

Divide and conquer

Tree-shaped recursion is not always wasteful. When the smaller problems do not overlap, it becomes a powerful strategy called divide and conquer:

1. Divide the problem into smaller, independent parts — typically two halves.
2. Conquer each part by solving it recursively.
3. Combine the partial answers into the answer for the whole.

FUNCTION sort(list)
    IF length of list ≤ 1 THEN
        RETURN list
    END IF
    left ← sort(first half of list)
    right ← sort(second half of list)
    RETURN merge(left, right)
END FUNCTION

This outline is merge sort, one of the fastest general sorting methods. Quicksort follows the same pattern; binary search is a simpler relative that recurses into only one half. All three are explained in Searching and Sorting.

When to use recursion

Recursion is the natural choice when the data itself is recursive: something that contains smaller things of the same kind. Examples are folders that contain folders, a web page's HTML elements nested inside each other, JSON documents, organization charts, and the trees used in data structures. A loop alone cannot easily handle nesting of unknown depth; a recursive function handles every level with the same few lines.

def nested_sum(items):
    total = 0
    for item in items:
        if isinstance(item, list):
            total += nested_sum(item)    # a list inside: recurse into it
        else:
            total += item                # a plain number: add it
    return total


# Boxes of parts, some packed inside other boxes
order = [12, [3, 4], [[5], 6], []]
print(nested_sum(order))

30

Here the base case is implicit: a list that contains no other lists makes no recursive calls. Prefer a loop when the problem is a straight sequence (counting, summing a flat list, repeating until a condition holds), when the depth can become large, or when speed matters — function calls cost more than loop steps in most languages.