Recursion explained: how it works, with Python examples

What problem recursion solves

Some problems are defined in terms of themselves. A folder contains files and other folders. A tree node has child trees. The factorial of n is n times the factorial of n − 1. Writing these with plain loops often needs an explicit stack of pending work; recursion lets the language keep that stack for you.

A recursive function has two parts:

• Base case: the smallest input, answered directly. For factorial, 0! = 1.
• Recursive case: reduce the problem, call the function on the smaller part, and combine the result. For factorial, n! = n × (n − 1)!.

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

The call stack, traced step by step

Each call gets its own frame on the call stack, holding its own copy of n. Calls go down until the base case, then the results come back up in reverse order.

The stack depth here is n + 1 frames, so the extra space is O(n) even though no list is created.

Recursion on nested data

Recursion is most useful when the shape of the data is itself recursive. This function sums all numbers in a list that may contain other lists, at any depth.

def deep_sum(items):
    total = 0
    for x in items:
        if isinstance(x, list):
            total += deep_sum(x)   # same problem, smaller piece
        else:
            total += x
    return total
print(deep_sum([1, [2, 3], [4, [5, [6]]]]))   # 21

The same pattern walks a directory tree, a JSON document, an HTML DOM or a binary tree: handle the current node, then recurse into each child.

def power_set(items):
    if not items:
        return [[]]
    rest = power_set(items[1:])
    return rest + [[items[0]] + s for s in rest]
print(power_set([1, 2, 3]))
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Complexity of recursive functions

Estimate the cost as (number of calls) × (work per call). Space is at least the maximum stack depth.

Divide-and-conquer recurrences such as T(n) = 2T(n/2) + O(n) for merge sort solve to O(n log n). A function that makes two calls on n − 1 grows exponentially.

Memoization: stop repeating work

The naive Fibonacci function recomputes the same values many times: fib(5) calls fib(3) twice and fib(2) three times. Caching each result the first time it is computed turns exponential time into linear time. Python's functools.lru_cache (or functools.cache, Python 3.9+) does this with one decorator.

from functools import lru_cache
def fib_slow(n):
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
print(fib_slow(20))   # 6765, about 22,000 calls
print(fib(90))        # 2880067194370816120, 91 distinct calls

Memoized recursion is the top-down form of dynamic programming. The bottom-up form fills a table with a loop instead.

Recursion limits and converting to a loop

You can raise the limit with sys.setrecursionlimit(), but a very deep recursion can still crash the interpreter. For input that may be deep, such as a linked list of a million nodes or a degenerate tree, rewrite the function with a loop and an explicit stack.

def deep_sum_iter(items):
    total, stack = 0, [items]
    while stack:
        current = stack.pop()
        for x in current:
            if isinstance(x, list):
                stack.append(x)
            else:
                total += x
    return total
print(deep_sum_iter([1, [2, 3], [4, [5, [6]]]]))   # 21

Common mistakes

• Missing or unreachable base case, for example factorial(-1) with the code above never reaches 0 and ends in RecursionError.
• A recursive case that does not shrink the input, such as calling f(n) from f(n).
• Forgetting to return the recursive result: factorial(n - 1) without return gives None.
• Copying data on every call. items[1:] copies the list, so recursing on slices of a long list costs O(n²) time; pass an index instead.
• Using a mutable default argument such as def f(x, seen=[]) to carry state between calls; the same list is shared by every call to the function.

When to use recursion

Use recursion when the data or the problem is naturally recursive: trees, graphs (depth-first search), nested structures, parsing expressions, backtracking (permutations, N-Queens, sudoku) and divide and conquer (merge sort, quicksort, binary search). Use a loop when the problem is a simple sequence, or when the depth can grow with the input size in Python.

In interviews, recursion questions often check that you can state the base case, the recursive case, the time and space cost including the stack, and when memoization helps.