Recursion

Why this matters

Some problems are naturally described in terms of smaller versions of themselves: a folder contains files and other folders; an expression like (2 + 3) * (4 - 1) contains smaller expressions; to sort a list you can sort two halves and merge them. A recursive function solves such problems by calling itself on the smaller pieces. Recursion is also the best way to really understand the call stack, which you met in lesson 1, and you will need it later for tree-shaped data such as JSON documents and directory trees.

A function that calls itself

def countdown(n):
    if n == 0:
        print("liftoff")
        return
    print(n)
    countdown(n - 1)

countdown(3)

3
2
1
liftoff

Every recursive function has two parts:

• a base case: an input simple enough to answer directly, without recursing (n == 0);
• a recursive case: reduce the problem to a smaller instance and call the function on that (countdown(n - 1)).

Each recursive call must move toward the base case. If it does not, the recursion never ends.

Recursion that returns values

Factorial is the classic example: 5! = 5 * 4 * 3 * 2 * 1, and by definition 0! = 1. Notice that 5! = 5 * 4!. That observation is the recursive case:

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

print(factorial(5))

120

What happens underneath: the stack grows and shrinks

Recall that each call gets its own frame with its own local variables. That is what makes recursion work: each active call of factorial has its own n. Here is the stack at its deepest point for factorial(3):

  factorial(0)   n=0   -> returns 1            <- top
  factorial(1)   n=1   waiting for factorial(0)
  factorial(2)   n=2   waiting for factorial(1)
  factorial(3)   n=3   waiting for factorial(2)
  <module>             waiting for factorial(3)

Then the stack unwinds, each frame finishing its multiplication with the value returned from above:

  factorial(0) returns 1
  factorial(1) returns 1 * 1 = 1
  factorial(2) returns 2 * 1 = 2
  factorial(3) returns 3 * 2 = 6

The work of multiplying happens on the way back, after the inner calls return. A helpful way to trace recursive code by hand is to write each call on its own line, indented, as above.

You can make the stack visible by printing with indentation proportional to depth:

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

factorial(3)

factorial(3)
  factorial(2)
    factorial(1)
      factorial(0)
      -> 1
    -> 1
  -> 2
-> 6

The recursion limit

Frames take memory, and CPython's frames for Python calls also use part of the C stack. To fail cleanly rather than crash the whole interpreter, CPython caps recursion depth:

import sys
print(sys.getrecursionlimit())

1000

Exceed it and you get:

Traceback (most recent call last):
  File "demo.py", line 4, in <module>
    countdown(5000)
  File "demo.py", line 3, in countdown
    countdown(n - 1)
  File "demo.py", line 3, in countdown
    countdown(n - 1)
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

You can raise the limit with sys.setrecursionlimit(5000), but that treats the symptom. If you hit it, either the base case is missing or wrong, or the problem is too deep for recursion in Python and a loop is better. Unlike some languages, Python does not do tail-call optimization: even a recursive call in the last position of a function uses a new frame.

Recursion versus loops

Anything written recursively can be written with a loop, and vice versa. For simple linear problems in Python, loops are usually better: no depth limit, and less overhead per step (each call has to create a frame).

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

Recursion shines when the problem branches: each step leads to several smaller subproblems. For example, counting the ways to climb n stairs taking 1 or 2 steps at a time:

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

print(ways(10))

89

This is short and mirrors the reasoning ("the last step was either 1 or 2 stairs"). But beware: ways(n - 1) and ways(n - 2) recompute the same smaller values again and again, so the number of calls grows exponentially; ways(35) takes seconds. The fix (caching results, called memoization) appears in the standard library tour with functools.cache.

Recursion can also make a problem cheaper when each step shrinks the input a lot. Halving instead of subtracting one, as in the fast exponentiation exercise, turns 1000 steps into about 15. That idea, "divide and conquer", underlies binary search and the fastest sorting algorithms.

How to write a recursive function

1. Find the base case(s): the smallest inputs, answered directly (0, 1, empty string, single digit).
2. Assume the function already works for smaller inputs (this is the leap of faith). How would you use the answer for n - 1 (or n // 10, or half the input) to answer for n?
3. Check that every path reaches a base case: the argument must shrink toward it on every call.
4. Test small cases by hand: 0, 1, 2.

Common mistakes

• No base case, or one that is never reached (for example if n == 0 when n jumps by 2 from an odd start): RecursionError.
• Forgetting to return the recursive result. factorial(n - 1) on its own computes a value and discards it, so the caller gets None, and then n * None raises TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'.
• Recomputing subproblems in branching recursion, making it exponentially slow.
• Using recursion for deep linear problems (walking a 100,000-line input one line per call). Use a loop.

Recap

• A recursive function calls itself on a smaller input; it needs a base case and a recursive case that moves toward it.
• Each call has its own frame on the call stack; results combine as the stack unwinds.
• CPython limits depth (about 1000 by default) and raises RecursionError; there is no tail-call optimization.
• Prefer loops for simple linear repetition; use recursion for naturally recursive or branching problems, and for divide-and-conquer.

Going further: write a recursive fib(n) and count how many calls fib(25) makes using a global counter. Then read about functools.cache in the standard library docs and watch the count collapse.