Recursion Fundamentals

Base cases, the call stack, tail recursion, and learning to think in terms of smaller subproblems

Introduction

A recursive function is one that solves a problem by calling itself on a smaller version of that same problem. It can feel circular the first time you see it, but it isn't: every valid recursive function is guaranteed to eventually stop, because each call works on a strictly smaller piece of the problem until it hits a case simple enough to answer directly. Recursion isn't just a coding trick either, it's how Python itself keeps track of function calls under the hood, using exactly the stack structure from Lesson 4.

Anatomy of a Recursive Function

Every correct recursive function needs exactly two parts:

Base Case

The simplest possible input, answered directly, with no further recursive calls. This is what stops the recursion.

Recursive Case

Breaks the problem into a smaller version of itself, then calls the function again on that smaller piece.

The classic first example is factorial: n! is n times the factorial of everything smaller than it, down to a base case of 1.

def factorial(n: int) -> int:
    if n <= 1:
        return 1                       # base case: stops the recursion
    return n * factorial(n - 1)        # recursive case: smaller subproblem

print(factorial(5))

Expected Output:

Forget the Base Case and You Get Infinite Recursion

Without the if n <= 1 check, factorial would call itself forever, or until Python runs out of stack space and raises a RecursionError. A missing or unreachable base case is the single most common recursion bug.

The Call Stack

Every time a function calls another function (including itself), Python pushes a new stack frame onto the call stack, holding that call's local variables and its return address. When a call finishes, its frame is popped off and control returns to whoever called it. This is the exact LIFO structure from Lesson 4, just managed by the Python interpreter instead of your own code.

Call Stack for factorial(3)

Figure 1: Each pending call waits on a stack frame until the one above it returns

factorial(1) returns first, since it's on top. Then factorial(2) can finish its multiplication and return. Then factorial(3). The results unwind back down the stack in the reverse order the calls were pushed, LIFO in action.

factorial(3): Calls Down, Returns Back Up

Figure 2: Calls stack up left to right (solid). Then they unwind right to left with return values (dashed): f(1) returns 1, f(2) multiplies by its n to get 2, and f(3) then multiplies by 3 to reach the final 6.

Recursion Depth Limits

Every stack frame uses real memory, and Python caps how deep the call stack can go to avoid crashing the interpreter. By default, that limit is 1000 frames:

import sys

print(sys.getrecursionlimit())

def count_up(n: int, limit: int) -> int:
    if n >= limit:
        return n
    return count_up(n + 1, limit)

try:
    count_up(0, 10_000)
except RecursionError as e:
    print("RecursionError:", e)

Expected Output:

1000
RecursionError: maximum recursion depth exceeded

Note: sys.setrecursionlimit() can raise this ceiling, but that just delays the problem, it doesn't fix it. If a recursive function can run deep enough to matter, an iterative rewrite is usually the better fix.

Tail Recursion (and Why Python Doesn't Optimize It)

A function is tail recursive when its recursive call is the very last thing it does, there's no pending multiplication or other work left after the call returns. Some languages detect this pattern and reuse the current stack frame instead of pushing a new one, a technique called tail-call optimization (TCO), which lets tail-recursive functions run in constant stack space. Scheme is the textbook example, its language specification actually requires proper tail calls, not just permits them as an optimization.

def factorial_tail(n: int, accumulator: int = 1) -> int:
    if n <= 1:
        return accumulator
    # The recursive call is the very last action, nothing happens after it returns
    return factorial_tail(n - 1, n * accumulator)

CPython Does Not Have TCO

Writing a function in tail-recursive style does not help in CPython. It still pushes one stack frame per call and still hits the same recursion limit:

try:
    factorial_tail(10_000)
except RecursionError:
    print("Still fails: CPython performs no tail-call optimization")

Expected Output:

Still fails: CPython performs no tail-call optimization

If you actually need to process deep or unbounded input, convert the recursion into a loop. The iterative version does the same work with a single stack frame, no matter how large n gets:

def factorial_iterative(n: int) -> int:
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Handles n = 10_000 without any RecursionError, and without a deep call stack
factorial_iterative(10_000)

Practical Pattern: Flattening a Nested List

Recursion shines whenever a structure can contain more of itself, exactly the case for a list that might hold other lists nested to an unknown depth. An iterative solution would need to manage its own explicit stack; recursion gets that for free from the call stack.

def flatten(nested: list) -> list[int]:
    result: list[int] = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))   # recursive case: dig one level deeper
        else:
            result.append(item)            # base case: a plain value
    return result

print(flatten([1, [2, 3, [4, 5]], 6]))

Expected Output:

[1, 2, 3, 4, 5, 6]

The base case is "this item isn't a list", just append it. The recursive case is "this item is a list", flatten it first, then merge the results in.

Bonus: The Tower of Hanoi

Move n disks from one peg to another, using a spare peg, never placing a larger disk on a smaller one. The recursive insight: to move n disks, move the top n - 1 out of the way, move the largest disk, then move those n - 1 back on top.

def hanoi(n: int, source: str, target: str, auxiliary: str) -> list[str]:
    if n == 0:
        return []                                          # base case: no disks to move

    # Move the top n-1 disks out of the way, onto the spare peg
    moves = hanoi(n - 1, source, auxiliary, target)
    moves.append(f"Move disk {n} from {source} to {target}")
    # Move those n-1 disks from the spare peg onto the target peg
    moves.extend(hanoi(n - 1, auxiliary, target, source))
    return moves

moves = hanoi(3, "A", "C", "B")
for move in moves:
    print(move)
print(f"Total moves: {len(moves)}")

Expected Output:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Total moves: 7

Each additional disk roughly doubles the number of moves, 2ⁿ - 1 in total. That's the O(2ⁿ) exponential growth from Lesson 1, showing up naturally from a three-line recursive function.

Key Takeaways

Every recursive function needs a base case and a recursive case - a missing base case means infinite recursion
Recursion is powered by the call stack - the exact LIFO structure from Lesson 4, one frame per pending call
Python's default recursion limit is 1000 frames - deep recursion raises RecursionError, not a silent failure
CPython has no tail-call optimization - writing "tail recursive" code doesn't save stack space here, unlike in some other languages
When depth is a real concern, convert to a loop - iteration does the same work in constant stack space

Back to "Stacks and Queues"

Data Structures & AlgorithmsLesson 5

Next: "Hash Tables and Hashing"