Recursion

Why it matters

Some problems are naturally made of smaller copies of themselves: a folder contains folders, a tree contains subtrees, a nested JSON document contains nested documents, and merge sort sorts two halves. RecursionA function solving a problem by calling itself on a smaller piece of the same problem., a function that calls itself on a smaller piece of the problem, is the cleanest way to write code for these shapes. You need it for trees and graphs in the next two lessons and for dynamic programming later.

The core idea

Every recursive function has two parts:

1. Base caseAn input small enough to answer directly, with no further recursive calls, that stops the recursion.: an input small enough to answer directly, with no further calls.
2. Recursive caseThe part of a recursive function that breaks the problem into a smaller version, calls itself and uses the result.: break the problem into a smaller version, call the function on it, and use the result.

The recursive case must always move toward the base case, or the function never stops.

def factorial(n):
    if n <= 1:                     # base case: 0! = 1! = 1
        return 1
    return n * factorial(n - 1)    # smaller problem: n - 1

How it runs: the call stack

Each call gets its own copy of its local variables and waits on the call stack until the call it made returns.

factorial(4)
  4 * factorial(3)
        3 * factorial(2)
              2 * factorial(1)
                    return 1         <- base case
              return 2 * 1 = 2
        return 3 * 2 = 6
  return 4 * 6 = 24

The calls go down until the base case, then the answers come back up. If there is no base case, Python stops you with RecursionError: maximum recursion depth exceeded (the default limit is about 1,000 calls deep).

Worked example 1: sum of digits

The digits of 482 add up to 4 + 8 + 2 = 14. The last digit is n % 10 and the rest is n // 10:

def sum_digits(n):
    if n < 10:                              # one digit: answer directly
        return n
    return n % 10 + sum_digits(n // 10)

sum_digits(482)   # 2 + sum_digits(48) = 2 + 8 + sum_digits(4) = 14

Worked example 2: flattening nested lists

[1, [2, [3, 4]], 5] should become [1, 2, 3, 4, 5]. You do not know how deep the nesting goes, which is exactly when recursion beats loops.

def flatten(items):
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))    # a smaller problem of the same shape
        else:
            result.append(item)
    return result

Here the base case is implicit: a list with no inner lists makes no further calls, and an empty list returns [] straight away.

Worked example 3: counting paths

How many ways can you climb n stairs taking 1 or 2 steps at a time? The last move was either a 1-step (from stair n - 1) or a 2-step (from stair n - 2), so:

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

It is correct but slow: climb(40) repeats the same sub-calls millions of times. You will fix that with memoisation in the dynamic programming lesson.

How to write a recursive function

1. Write the signature and say in words what it returns. "sum_digits(n) returns the sum of the digits of n."
2. Find the smallest inputs and answer them directly (0, 1, empty list, a leaf node).
3. Assume the function already works on a smaller input (this is the "leap of faithWriting the recursive case by assuming the function already works on the smaller input.") and write how to use that answer.
4. Check that every call gets smaller. n - 1, n // 10, a sublist, a child node.
5. Test the base cases first, then a slightly bigger input by tracing by hand.

Recursion or a loop?

Anything recursive can be written with a loop and an explicit stack, and Python does not optimise deep recursion. Use recursion when the data is nested or tree-shaped and the depth is modest (hundreds, not hundreds of thousands). Use a loop for simple counting down a long sequence.

Common mistakes

• No base case, or one that is never reached, for example factorial(-1) with a base case of n == 1 only. Use n <= 1.
• Forgetting return. factorial(n - 1) on its own line computes the answer and throws it away.
• Not making the problem smaller, such as calling f(n) from inside f(n).
• Sharing a mutable default like def f(items, out=[]). The same list is reused between calls; build and return a new list instead.

Quick recap

• Recursion = base case + a call on a smaller input.
• Calls stack up until the base case, then results return in reverse order.
• Trust the smaller call, combine its answer, and test the base cases first.
• Python's depth limit is about 1,000; use loops for very long chains.

Try it

In the Do tab, write factorial, sum_digits and flatten recursively. The checks include the base cases (0, a single digit, an empty list) and deep nesting.