Recursion snippets

Recursion is a function that solves a problem by calling itself on a smaller piece of the same problem. It fits data that nests to an unknown depth, like a nested list or a tree, where a plain loop cannot know how deep to go.

The two parts every recursion needs

Every recursive function has a base case and a recursive case. The base case is the smallest input, the one you can answer without recursing, and it stops the calls. The recursive case reduces the problem toward that base case and calls the function again.

def factorial(n):
    if n <= 1:              # base case: stop here
        return 1
    return n * factorial(n - 1)   # recursive case: a smaller problem

factorial(4)                # → 24   (4 * 3 * 2 * 1)

Miss the base case, or fail to move toward it, and the calls never stop. Python raises RecursionError once the stack gets too deep (the default limit is 1000 nested calls).

How the call stack works

Each call waits, paused, while the call it made runs. Those paused calls pile up on the call stack, and each one is a frame holding that call’s own variables. When a call returns, its frame is freed and the caller picks up where it left off.

  factorial(4)                 frame 1 opens, waits on factorial(3)
    factorial(3)               frame 2 opens, waits on factorial(2)
      factorial(2)             frame 3 opens, waits on factorial(1)
        factorial(1)           frame 4 opens  → base case, returns 1
      returns 2 * 1 = 2        frame 3 frees
    returns 3 * 2 = 6          frame 2 frees
  returns 4 * 6 = 24           frame 1 frees

The stack grows on the way down and unwinds on the way back up. The most frames open at once is the depth of the recursion, which is where the O(depth) memory cost of a recursive solution comes from.

A recursion that walks nested data

The natural use: data of arbitrary depth. Flattening a nested list handles one level and recurses into anything that is still a list.

def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):        # a sublist: recurse into it
            result.extend(flatten(item))
        else:
            result.append(item)           # a plain value: keep it
    return result

flatten([1, [2, [3, 4]], 5])   # → [1, 2, 3, 4, 5]

The base case here is quiet: a list with no sublists never recurses, it just appends its values, and an empty list returns an empty list.

Recursion depth is limited

Python caps recursion at about 1000 nested calls by default, and each call uses stack memory. For data that is deep rather than wide, or for very long sequences, an iterative version with an explicit list or collections.deque as a stack avoids the limit. Reach for recursion when the depth is modest and the recursive shape makes the code clearer.