Python — RecursionError: maximum recursion depth exceeded

Find the missing or unreachable base case, convert deep recursion to an explicit stack, and avoid raising the recursion limit as a substitute for a fix.

intermediatedebuggingpythonrecursion

Symptoms

RecursionError: maximum recursion depth exceeded
The traceback repeats the same function frame hundreds of times
The failure appears only for deep trees, linked lists, or self-referential data
The code works for small inputs and fails for production data

Possible causes

The base case is missing, unreachable, or does not change the input
The recursive call passes the same arguments without reducing the problem
The input contains a cycle and the function does not track visited nodes
The algorithm is naturally deep, such as traversing a long list or deeply nested JSON
A library callback recursively re-enters the same function

Diagnosis steps

Read the repeating frame and the argument values

python -X dev script.py

Interpretation

The repeated frame names the recursive function. Print the argument at each call or use a depth counter to see whether it changes.

Check the recursion limit and the input depth

python -c "import sys; print(sys.getrecursionlimit())"

Interpretation

The default limit is about 1000. An input deeper than the limit will fail even with a correct base case.

Test with a small input and inspect for cycles

python -c "import sys; sys.setrecursionlimit(10000); ..."

Interpretation

Raising the limit can confirm depth as the cause, but it risks a C stack overflow if used as the fix.

Root cause

The function calls itself more times than the interpreter's recursion limit allows. Either the base case never terminates the recursion, or the input is legitimately deeper than the limit.

Fix

Fix the base case and ensure every recursive call makes progress. For legitimately deep inputs, rewrite the traversal with an explicit stack or a queue. Track visited nodes for graphs and cyclic structures. Raise the limit only as a temporary diagnostic, never as the only fix.

Risk note

sys.setrecursionlimit can crash the interpreter with a segmentation fault when the C stack is exhausted. It is not a substitute for an iterative algorithm.

Verify the fix

Add tests for the smallest base case, a deep input beyond the former limit, and a cyclic structure. Confirm the iterative version returns the same result and that memory stays bounded. Run under -X dev so warnings are visible.

The base case is the first suspect

A RecursionError means the function called itself more than the interpreter allows. The traceback repeats the same frame, which points to the recursion but not to the reason. Print the arguments or add a depth counter. If the argument never reaches the base case, the recursion is unbounded; if it does but the input is deeper than the limit, the algorithm needs an explicit stack.

def depth(node):
    if node is None:
        return 0
    return 1 + depth(node.left)  # missing right branch is a logic bug,
                                 # but a cycle or a very deep tree is the usual depth problem

Cycles and shared nodes

Graphs and object trees can contain cycles. A recursive traversal without a visited set will loop until the limit. Track visited ids for graphs, or carry a path set for trees where a node may appear twice. The fix is not a larger limit; it is to stop revisiting.

Convert deep recursion to iteration

For a long list or deeply nested document, use an explicit stack:

def walk(root):
    stack = [root]
    seen = set()
    while stack:
        node = stack.pop()
        if node is None or id(node) in seen:
            continue
        seen.add(id(node))
        yield node
        stack.extend(node.children)

This keeps memory on the heap, avoids the interpreter recursion limit, and makes cycle handling explicit. Some algorithms are easier to express recursively; for shallow inputs, recursion is fine. The choice should depend on the input depth, not on style alone.

Do not raise the limit as a fix

sys.setrecursionlimit(100000) can push the C stack past its limit and crash the process with a segmentation fault instead of a clean exception. Raising it briefly as a diagnostic is acceptable; shipping it as the fix is not. Fix the base case, add cycle detection, or use an iterative traversal, then verify with an input deeper than the original failure.