Python Recursion: Base Cases, Recursion Limit and Memoization

How does recursion work in Python?

A recursive Python function calls itself on a smaller version of its input and stops at a base case small enough to answer directly. Each call adds a frame to the call stack, and the frames unwind as the calls return. CPython limits the depth to 1 000 frames by default and does not eliminate tail calls, so deep recursion over long inputs is better written as a loop.

Lesson

A recursive function calls itself on a smaller version of its input and stops at a case small enough to answer directly. Python supports it like any language, with one limit that matters more here than elsewhere: the interpreter refuses to nest calls more than about 1 000 deep by default, and the stack it uses is real memory. This lesson gives the two-part shape of every recursive function, shows what the call stack does on each call, explains RecursionError and sys.setrecursionlimit, and turns exponential recursion into linear with memoisation — by hand and with functools.cache.

The shape

def factorial(n):
    if n <= 1:                    # base case: answered directly
        return 1
    return n * factorial(n - 1)   # recursive case: a smaller problem, plus one step

Two questions design any recursive function. What is the smallest input, and what is its answer? — the base case, written first, because a recursion without one never ends. If I had the answer for a smaller input, how would I get the answer for this one? — the recursive case, which must move toward the base case on every path.

def sum_digits(n):
    return n if n < 10 else n % 10 + sum_digits(n // 10)

def flatten(xs):                  # recursion over nested structure
    out = []
    for x in xs:
        if isinstance(x, list):
            out.extend(flatten(x))
        else:
            out.append(x)
    return out

Recursion over structure — nested lists, trees, JSON — is where it is clearly the right tool: the shape of the code follows the shape of the data. Recursion over numbers (factorial, fib) is usually a loop in disguise and is shown for teaching.

The call stack

Each call creates a frame holding its parameters and locals; the frame lives until the call returns. factorial(4) stacks four frames — n=4, n=3, n=2, n=1 — then unwinds, multiplying on the way back:

factorial(4)
  factorial(3)
    factorial(2)
      factorial(1) -> 1
    -> 2 * 1 = 2
  -> 3 * 2 = 6
-> 4 * 6 = 24

Everything after the recursive call in the body runs during the unwind, in reverse order of the calls — which is why a function that prints before recursing prints top-down and one that prints after recursing prints bottom-up, and why reversing a list recursively is "the reverse of the rest, then the first element".

The recursion limit

CPython caps the depth at sys.getrecursionlimit() — 1 000 by default — and raises RecursionError: maximum recursion depth exceeded when a call would exceed it. A recursion with no base case hits it immediately; a correct recursion over a long list (sum_list(xs) recursing once per element) hits it at a thousand elements. sys.setrecursionlimit(200_000) raises the cap and works on this track's judge for depths in the tens of thousands, but the cap exists because each Python frame costs real memory and a deep enough recursion crashes the interpreter rather than raising. The safer answers, in order: make the recursion shallow (divide in half rather than peeling one element — depth log n), or rewrite it as a loop with an explicit stack (a list you append to and pop from), which is what any recursive traversal becomes when the input is large.

Python does not optimise tail calls: return f(n - 1) still adds a frame. A tail-recursive function is exactly the one that converts to a while loop mechanically, so convert it.

Memoisation

def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)      # fib(35) makes ~30 million calls

The naive version recomputes fib(k) exponentially many times. Remembering each result the first time it is computed makes every call after the first O(1):

from functools import cache

@cache
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)      # fib(500) is instant

@cache (3.9; @lru_cache(maxsize=None) before it) wraps the function with a dictionary keyed by the arguments. The arguments must be hashable — ints, strings, tuples, not lists — and the function must be pure: same arguments, same result, no side effects. fib.cache_info() reports hits and misses; fib.cache_clear() empties it. The hand-written version is a dict parameter or a module-level dict checked at the top of the function:

def fib(n, memo={}):        # a mutable default used on purpose — the cache should persist
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Memoised recursion is top-down dynamic programming; the loop that fills a table from the base case up is bottom-up, uses no stack, and is what to reach for when the depth would be large.

Generating combinations

Recursion is the natural way to enumerate choices — every subset, every permutation, every path — because each level of the recursion makes one decision:

def subsets(xs):
    if not xs:
        return [[]]
    rest = subsets(xs[1:])
    return rest + [[xs[0]] + s for s in rest]

print(subsets([1, 2, 3]))
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

itertools.permutations, combinations and product (Module 11) do the standard ones; write the recursion when there is a constraint to prune on — the backtracking pattern.

Pitfalls

• No base case, or a recursive case that does not shrink the input on some path.
• Recursing once per element over an input that can be long — RecursionError at ~1 000.
• Building a new list on every call (xs[1:]) — quadratic; pass an index instead.
• Memoising a function with side effects or unhashable arguments.
• Expecting tail-call elimination.
• Reading RecursionError as "recursion is too slow" — it is too deep.

Key takeaways

• Base case first, then a recursive case that strictly shrinks the input.
• Each call is a frame; code after the recursive call runs during the unwind, in reverse.
• The default depth limit is 1 000; raise it with sys.setrecursionlimit for the judge, or recurse on halves, or use an explicit stack.
• @functools.cache memoises a pure function with hashable arguments — exponential to linear.
• Recursion fits nested data and choice enumeration; numeric recursion is usually a loop.

Common questions

What is the maximum recursion depth in Python?

CPython's default limit is 1 000 frames, reported by sys.getrecursionlimit(); exceeding it raises RecursionError: maximum recursion depth exceeded. sys.setrecursionlimit raises the cap, but each frame costs real memory and a deep enough recursion can crash the interpreter, so recursing on halves or using an explicit stack is safer.

How do I fix RecursionError: maximum recursion depth exceeded?

First check for a missing base case, or a recursive case that does not shrink the input on some path. If the recursion is correct but too deep, as when it recurses once per element of a long list, rewrite it as a loop with an explicit stack, recurse on halves for log n depth, or raise the limit with sys.setrecursionlimit.

Does Python have tail call elimination?

No. CPython does not eliminate tail calls, so return f(n - 1) still adds a stack frame and a long tail-recursive chain hits the recursion limit. A tail-recursive function converts mechanically into a while loop, and that loop is the Python way to write it.

How do I cache a recursive function in Python?

Decorate it with @functools.cache (Python 3.9; @lru_cache(maxsize=None) before that), which stores each result in a dictionary keyed by the arguments. This memoisation turns the exponential naive fib into a linear one. The arguments must be hashable and the function pure: same arguments, same result, no side effects.

Exercises

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

flat: 1 2 3 4 5
depth: 3

3
10
50
90

55
12586269025
2880067194370816120

In this module: Functions

• Defining functions — def, return and functions as values
• Parameters and arguments — positional, keyword, defaults, *args and **kwargs
• Scope and closures — LEGB, global, nonlocal and late binding
• Recursion — base cases, the call stack and memoisation (this lesson)
• Lambdas and higher-order functions
• Type hints and docstrings — the contract a function publishes
• Checkpoint — Functions