Recursion in Python: How It Works and When to Avoid It

How a recursive function calls itself

A recursive function solves a problem by calling itself on a smaller version of that same problem. The classic introductory example is factorial:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))   # 120

factorial(5) calls factorial(4), which calls factorial(3), and so on down to factorial(0), which returns immediately without calling itself further. The results then multiply back up as each call returns to whichever call invoked it.

The base case, and why it matters

Every correct recursive function needs at least one base case — a condition under which it returns a value directly instead of calling itself again. n == 0 is the base case in factorial. Without one, or with a base case that the recursive calls never actually reach, the function recurses forever, or in practice, until Python's recursion limit is hit:

def broken_countdown(n):
    print(n)
    return broken_countdown(n - 1)   # no base case -- never stops

Each recursive call must move strictly closer to the base case — here, by decrementing n — or the recursion cannot terminate no matter how the base case itself is written.

The call stack behind the scenes

Every function call, recursive or not, pushes a new frame onto the call stack — a record of that call's local variables and where execution should resume once it returns. A recursive function accumulates one frame per pending call:

def factorial(n):
    if n == 0:
        return 1
    result = n * factorial(n - 1)   # this call is still "open" while
    return result                   # factorial(n - 1) runs

While computing factorial(5), five frames stack up before any of them returns a value, and each holds onto its own n and partial result until the calls below it finish and unwind back up the stack.

Python's recursion limit

CPython caps the call stack depth — by default around 1000 frames — and raises RecursionError if that limit is exceeded, to prevent an unbounded recursive call from crashing the interpreter with a stack overflow:

import sys
print(sys.getrecursionlimit())   # 1000, typically

def count_up(n):
    if n <= 0:
        return
    count_up(n - 1)

count_up(2000)   # raises RecursionError

The limit can be raised with sys.setrecursionlimit(), but this only postpones the problem and increases the risk of a real, harder-to-diagnose interpreter crash — it does not add memory or resolve an algorithm that genuinely needs that much depth.

When to avoid recursion

Python has no automatic tail-call optimisation — unlike some other languages, a recursive call that happens to be the last operation in a function still consumes a new stack frame. For problems whose natural recursion depth scales with input size, an iterative loop is usually the safer choice:

# Recursive: risks RecursionError on a very long list.
def sum_list(items):
    if not items:
        return 0
    return items[0] + sum_list(items[1:])

# Iterative: constant stack usage regardless of length.
def sum_list_iterative(items):
    total = 0
    for item in items:
        total += item
    return total

For recursive functions that repeat the same sub-calculations — like naive Fibonacci — functools.lru_cache or an explicit memo dictionary avoids exponential re-work without abandoning the recursive structure entirely. Recursion still earns its place for genuinely tree-shaped or naturally nested problems, such as walking a directory tree or a nested JSON structure, where the depth is small and the recursive form matches the data far more clearly than an iterative rewrite would.

Tracing recursive calls while debugging

A recursive function that misbehaves is often easiest to understand by printing its argument and depth at every call, indented to visually mirror the call stack:

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

factorial(3)
# factorial(3)
#   factorial(2)
#     factorial(1)
#       factorial(0)

The indentation makes it immediately visible how deep the recursion went and in what order calls were made, which is usually far faster than stepping through a debugger line by line for a bug that only shows up several calls deep. Once the logic is confirmed correct, the tracing print statement and the extra depth parameter are simply removed. The same technique also makes it obvious, at a glance, whether a suspected infinite recursion is actually looping on the same argument value rather than making genuine progress toward its base case.