Recursion - When a Function's Best Move Is to Call Itself

Helpful context:

• Functions & Scope - Reusable Code and Where Variables Live

Hold two mirrors facing each other and look inside. You see a hallway of reflections stretching into a vanishing point - each reflection contains an image of itself, slightly smaller, slightly darker, until it disappears into the distance.

This is self-reference. The image contains itself. The definition contains itself. It is a structure that should not be able to exist, and yet there it is, perfectly finite, perfectly stable, arising from an infinite regress that stops only because each copy is smaller than the last.

Recursion is the same idea applied to computation. A function calls itself. That call calls itself again. The calls nest until they reach a case small enough to answer directly, and then the answers propagate back up through the chain. The result is a technique of remarkable power and elegance - and, until you have built the right mental model, remarkable confusion.

Why Recursion Was Invented

Recursion was not a clever trick added to programming languages. It emerged naturally from the mathematics of computation. Alonzo Church’s lambda calculus (1936) and Kurt Gödel’s work on recursive functions preceded electronic computers by decades. When McCarthy designed Lisp in 1958, he made recursion the primary mechanism for repetition - not because it was fashionable, but because it was the most direct way to express computations defined inductively.

A factorial is defined inductively: 0! = 1, and n! = n × (n-1)!. The Fibonacci sequence is defined inductively: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). Tree traversal is defined inductively: process a node, then recursively process each child. These definitions are recursive - and recursive code reflects them directly:

def factorial(n):
    if n == 0:          # base case: the definition gives a direct answer
        return 1
    return n * factorial(n - 1)   # recursive case: reduce to a smaller instance

The code looks like the mathematical definition. This is not a coincidence.

The Two Mandatory Pieces

Every correct recursive function has exactly two components:

A base case - the simplest input where you return a result directly, without a recursive call. For factorial, that is n == 0. For tree traversal, it is an empty tree or a leaf node. For string reversal, it is an empty string.

A recursive case - the general case, where you call yourself with a strictly smaller or simpler input. The crucial word is strictly. If the recursive call does not make progress toward the base case, you have infinite recursion.

Forgetting the base case, or writing a recursive case that does not reduce the input, causes the function to call itself until Python raises:

RecursionError: maximum recursion depth exceeded

This is a stack overflow - the call stack ran out of space. We will get to why shortly.

Building the Mental Model

This is the hard part. Let me be direct about why recursion feels wrong at first: the human mind is not naturally comfortable with leaving a computation in a suspended state. When you read return n * factorial(n - 1), something in your brain wants to know what factorial(n - 1) is right now, before moving on. But you cannot know - it depends on another call, which depends on another call.

The trick is to stop trying to trace the execution. Instead, use inductive reasoning. Ask yourself:

1. Does the base case return the right answer? For factorial(0), yes - 1 is correct.
2. If factorial(n - 1) magically returns the right answer, does n * factorial(n - 1) return the right answer for n? Yes - by the definition of factorial.

That is all you need. If the base case is right and the recursive step is right given that the recursive call works, then the function is correct for all valid inputs, by induction. You do not need to trace the call chain.

This is the same reasoning mathematicians use when writing inductive proofs. Recursion is induction in code.

What Is Actually Happening: Stack Frames

Now for the mechanism. We covered stack frames in Functions & Scope - Reusable Code and Where Variables Live - every function call creates a frame on the call stack holding local variables and the return address. Recursive calls are no different:

factorial(4)
# Creates frame: n=4, waiting to compute 4 * factorial(3)
#   factorial(3)
#   Creates frame: n=3, waiting to compute 3 * factorial(2)
#     factorial(2)
#     Creates frame: n=2, waiting to compute 2 * factorial(1)
#       factorial(1)
#       Creates frame: n=1, waiting to compute 1 * factorial(0)
#         factorial(0)
#         Returns 1  ← base case, no more frames pushed
#       Returns 1 * 1 = 1
#     Returns 2 * 1 = 2
#   Returns 3 * 2 = 6
# Returns 4 * 6 = 24

The call stack grows as calls accumulate, then shrinks as they return. The deepest point - the moment just before the base case returns - is where the most frames exist simultaneously. For factorial(n), that is n+1 frames. For factorial(1000), that is 1001 frames.

Python’s default limit is 1000 frames (configurable via sys.setrecursionlimit). This is not arbitrary caution - each stack frame consumes memory, and the operating system allocates a fixed region for the call stack. Overflow it and the process crashes.

This is why recursion depth matters, and why recursion is poorly suited for processing flat, large collections.

Tree Recursion: Where It Gets Beautiful

The most compelling use case for recursion is data that is recursively defined - trees.

A tree node has a value and a list of children. Each child is itself a tree node. The structure is recursive. Code that processes it naturally mirrors that structure:

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []

def tree_sum(node):
    """Sum all values in a tree of arbitrary depth."""
    return node.value + sum(tree_sum(child) for child in node.children)

def tree_depth(node):
    """Return the maximum depth of the tree."""
    if not node.children:
        return 1
    return 1 + max(tree_depth(child) for child in node.children)

root = Node(1, [
    Node(2, [Node(4), Node(5)]),
    Node(3, [Node(6)])
])

print(tree_sum(root))    # 21
print(tree_depth(root))  # 3

Try writing tree_sum iteratively. You will need to manually manage a stack - pushing and popping nodes, accumulating results. The recursive version has no such bookkeeping because the call stack is the stack. The machine’s own architecture handles the state management.

This extends to depth-first search, parsing nested expressions, processing JSON or XML, generating permutations, and the divide-and-conquer algorithms (merge sort, quicksort, binary search) that appear throughout computer science.

The Exponential Cost Problem: Fibonacci

Fibonacci is the standard example of naive recursion going catastrophically wrong:

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

This is correct. It is also disastrously slow. fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) and fib(2). fib(3) is computed twice. fib(2) is computed three times. The call tree grows exponentially - computing fib(n) requires $O(2^n)$ calls.

The problem is overlapping subproblems: the same computation happens many times. The fix is memoization - cache results and reuse them:

import functools

@functools.lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(100))   # 354224848179261915075, computed instantly

lru_cache stores the return value for each set of arguments. The second time fib(3) is called, it returns the cached value immediately. This brings Fibonacci from $O(2^n)$ time to $O(n)$ time - solving 100 calls instead of $2^{100}$ calls.

This is the bridge to dynamic programming: when a recursive problem has overlapping subproblems, cache the results. The memoized recursion and the bottom-up dynamic programming table are two ways of solving the same structure.

Tail Recursion: The Optimization Python Does Not Have

There is a particular form of recursion called tail recursion, where the recursive call is the very last thing the function does - with no pending computation afterward:

# Tail recursive - the recursive call IS the return value
def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)   # last operation

Compare with the original:

# Not tail recursive - after the recursive call, we still need to multiply
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)   # must multiply after the call returns

In languages that implement tail call optimization (TCO) - Scheme, Haskell, most functional languages, modern JavaScript - tail recursive functions are automatically converted to loops by the compiler. No new stack frame is pushed; the current frame is reused. Tail recursion becomes O(1) stack space, making it safe for arbitrarily deep recursion.

Python does not do this. Guido van Rossum has explicitly stated he will not add TCO to Python, arguing that the resulting loss of stack traces makes debugging too difficult. This is a real design tradeoff - tail recursion eliminates stack overflow at the cost of opacity.

The consequence: if you write a tail-recursive function in Python, it still creates n stack frames. For deep recursion, convert it to a loop:

def factorial_iter(n):
    result = 1
    while n > 0:
        result *= n
        n -= 1
    return result

This is the iterative equivalent of the tail-recursive version. Same logic, no stack depth concern, faster in practice.

When to Use Recursion and When Not To

Reach for recursion when:

• The problem is recursively defined (trees, nested structures, grammars).
• The recursive solution is significantly clearer than the iterative equivalent.
• The input depth is bounded (file systems rarely exceed depth 20; a balanced binary search tree over a million elements has depth at most 20).
• The problem structure naturally produces divide-and-conquer: split, solve, combine.

Prefer iteration when:

• You are processing a flat data structure (a list, an array). Iterating 100,000 elements recursively will hit the recursion limit. A loop will not.
• Performance matters and you cannot afford the function call overhead.
• The recursion depth is proportional to input size and could be large.
• You are in Python and the elegant tail-recursive form cannot benefit from TCO.

Common gotcha: Python’s recursion limit is 1000, not 1000 per call chain - it is 1000 total active frames across all recursive calls. If your function calls another function which calls another, those all count against the limit.

Connection to Divide and Conquer, DFS, and Dynamic Programming

Recursion is not just a coding technique - it is the underlying structure of entire classes of algorithms.

Divide and conquer algorithms (merge sort, quicksort, binary search) recursively split a problem, solve the pieces, and combine the results. The recursion tree is the algorithm’s structure.

Depth-first search (DFS) on a graph is recursion over a tree-like structure: visit a node, then recursively visit unvisited neighbors. The call stack naturally maintains the path being explored.

Dynamic programming is memoized recursion made explicit. The recursive formulation identifies the structure; the memoization (or the bottom-up table) eliminates the redundant computation.

Every time you encounter these topics in algorithms, you are looking at recursion in a different outfit.

Read Next:

• Object-Oriented Programming - Structuring Code Around What It Represents