Recursion — Algorithms & Data Structures with Python

What recursion is

A function is a named block of code you can run by writing its name followed by parentheses, optionally passing it some values called arguments. Most functions call other functions. Recursion is what we call it when a function calls itself. That sounds circular, and it would be useless if it never stopped. The trick is that each call works on a smaller version of the same problem, and eventually the problem gets small enough that the answer is obvious and the function can answer directly without calling itself again.

Here is the shape of every recursive function:

def count_down(n):
    if n == 0:          # the easy case: answer directly
        print("done")
        return
    print(n)
    count_down(n - 1)   # the same problem, one step smaller

count_down(3)
# -> 3
# -> 2
# -> 1
# -> done

count_down(3) prints 3, then calls count_down(2), which prints 2, then calls count_down(1), and so on until count_down(0), which prints done and stops. The problem shrinks by one each time and is guaranteed to reach 0.

The two cases

Every correct recursive function has two parts.

Base case: the smallest version of the problem, where you know the answer without recursing. In count_down the base case is n == 0. It is the stopping condition.
Recursive case: everything else. Here the function does a little work and then calls itself on a smaller input, trusting that call to solve the smaller problem.

Why a missing base case is fatal

If there is no base case, or the input never actually reaches it, the function calls itself forever. This is infinite recursion. Python does not let it run truly forever; it stops the program with a RecursionError once too many calls pile up (more on that below).

def broken(n):
    print(n)
    broken(n - 1)   # no base case: nothing ever stops this

# broken(3) prints 3, 2, 1, 0, -1, -2, ... then:
# RecursionError: maximum recursion depth exceeded

A base case that the input can never reach is just as broken. broken(3) above does have a natural-looking floor of 0, but nothing checks for it, so it sails straight past into negative numbers.

The call stack

To understand how recursion runs, you need the call stack. Whenever any function is called, Python sets aside a small region of memory for that specific call, called a stack frame (or just “frame”). The frame holds that call’s own copy of its arguments and local variables. When the function returns, its frame is thrown away and control goes back to whoever called it.

“Stack” means last-in, first-out: the most recent call is the first to finish, like a stack of plates where you take from the top. With recursion, several frames for the same function exist at once, each with its own value of n.

Consider computing the sum 1 + 2 + ... + n recursively:

def sum_to(n):
    if n == 0:            # base case
        return 0
    return n + sum_to(n - 1)   # recursive case

print(sum_to(3))   # -> 6

Here is the stack growing and then shrinking for sum_to(3). Each call waits, paused, for the call below it to return a value before it can finish its own addition:

sum_to(3) = 3 + sum_to(2)
              sum_to(2) = 2 + sum_to(1)
                            sum_to(1) = 1 + sum_to(0)
                                          sum_to(0) = 0          <- base case returns 0
                            sum_to(1) = 1 + 0 = 1
              sum_to(2) = 2 + 1 = 3
sum_to(3) = 3 + 3 = 6

Each frame stays alive until the ones “below” it (deeper calls) return. That is why recursion uses memory proportional to how deep it goes. For sum_to(n) the depth is n, so it uses O(n) space on the stack even though it only does O(n) work.

Worked example: factorial

The factorial of a whole number n, written n!, is the product of all whole numbers from 1 up to n. So 4! = 4 * 3 * 2 * 1 = 24. By convention 0! = 1.

Factorial has a natural recursive definition: n! = n * (n - 1)!, and 0! = 1. That maps directly to code.

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

print(factorial(4))   # -> 24
print(factorial(0))   # -> 1

factorial(4) becomes 4 * factorial(3), which becomes 4 * (3 * factorial(2)), and so on down to factorial(0), which returns 1. Then the multiplications resolve back up.

Time: O(n), because it makes n calls each doing one multiplication. Space: O(n) for the stack of n frames.

Worked example: Fibonacci

The Fibonacci numbers are a sequence that starts 0, 1, and after that each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, .... We index from zero, so fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2, fib(4) = 3.

The definition has two base cases and one recursive case that calls itself twice:

def fib(n):
    if n < 2:                    # base cases: fib(0)=0, fib(1)=1
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(4))   # -> 3
print(fib(10))  # -> 55

This is correct but slow, and it is worth seeing exactly why. Because each call spawns two more calls, the work fans out into a tree. Trace fib(4) and every call branches into two more until it bottoms out at a base case:

graph TD
    A["fib(4)"] --> B["fib(3)"]
    A --> C["fib(2)"]
    B --> D["fib(2)"]
    B --> E["fib(1)"]
    C --> F["fib(1)"]
    C --> G["fib(0)"]
    D --> H["fib(1)"]
    D --> I["fib(0)"]

Look at how many times the same subproblem appears. fib(2) is computed twice (nodes C and D). fib(1) is computed three times. Nothing remembers a result once it is found, so the same work is redone again and again. As n grows, the number of repeated calls explodes.

This recursive fib runs in roughly O(2^n) time (the tree of calls nearly doubles in size for each extra level) and O(n) space (the stack only ever holds one root-to-leaf path at a time, and the deepest path is n frames). That exponential time is why this version is unusable for n much beyond 35 or so.

The fix is to store each answer the first time you compute it and reuse it, a technique called memoization. That is a topic for a later lesson; the recursion tree above is exactly the picture that motivates it. The repeated nodes are the wasted work memoization removes.

Recursion vs iteration

Iteration means solving a problem with a loop (for or while) instead of by calling a function on itself. Anything you can do with recursion you can also do with iteration, and vice versa. They are two ways to express repetition.

Here is Fibonacci written iteratively. It keeps only the last two values and walks forward:

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_iter(10))  # -> 55

This is O(n) time and O(1) space: one loop, and just two variables regardless of n. It beats the recursive version on both counts.

The trade-off, in general:

Recursion often matches the shape of a problem that is defined in terms of itself (trees, nested structures, divide-and-conquer). The code can be shorter and closer to the definition. The cost is a stack frame per level of depth, which is real memory and is limited.
Iteration uses constant stack space and has no depth limit beyond your patience. It can be less readable when the problem is naturally recursive.

A useful rule: reach for recursion when the data itself is recursive (a tree, a folder of folders). Reach for iteration when you are just repeating a step a known number of times.

Python’s recursion depth limit

Because every pending call holds a live stack frame, and memory is finite, Python caps how deep recursion may go. By default the limit is around 1000 nested calls. Exceed it and you get a RecursionError rather than a crash of the whole interpreter.

def deep(n):
    return deep(n + 1)

# deep(0)
# RecursionError: maximum recursion depth exceeded

You can inspect and raise the limit, but doing so is usually a sign you should rewrite the function iteratively instead:

import sys
print(sys.getrecursionlimit())   # -> 1000 (typical default)

Raising it with sys.setrecursionlimit is possible but risky: set it too high and a truly infinite recursion can exhaust real memory and crash the process. For deep-but-finite problems, prefer an iterative version.

Common pitfalls

No base case, or an unreachable one. The single most common bug. Make sure every recursive call moves the input strictly toward the base case, and that the base case is actually tested. n - 1 on a value that can go negative will overshoot a == 0 check; use <= 0 if negatives are possible.
Forgetting to return the recursive call. Writing factorial(n - 1) instead of return n * factorial(n - 1) computes the value and throws it away, so the function returns None.
Redoing the same work. Naive fib recomputes identical subproblems exponentially many times. If your recursion tree has repeated nodes, you likely want memoization.
Hitting the depth limit. Recursion depth of a few thousand will fail. Linear recursion over a large list (one frame per element) is a classic way to blow the stack; loop instead.
Assuming recursion is free. Each call costs a frame in memory and some overhead. For simple counting loops, iteration is both faster and lighter.

Practice

Write a recursive function power(base, exp) that computes base raised to the whole-number power exp (for example power(2, 5) is 32), using the fact that base**exp == base * base**(exp - 1) and base**0 == 1. State its time and space complexity.
Write a recursive function reverse_string(s) that returns the string s with its characters in reverse order (reverse_string("cat") returns "tac"). Hint: the reverse of a string is its last character followed by the reverse of everything before it, and the reverse of an empty string is the empty string.
Draw or write out, by hand, the recursion tree for fib(5). Count how many times fib(2) is called. Then explain in one sentence why an iterative version avoids that repetition.