RecursionError: Fix Max Depth Exceeded in Python

Your tree walk dies with RecursionError: maximum recursion depth exceeded, and the traceback is the same 4 lines repeated 250 times. The function works on every test tree. Production feeds it a 3,000-deep category chain — or a cycle two categories form by pointing at each other — and the stack blows past 1000 frames in milliseconds.

Python caps the call stack at 1000 frames by default, a deliberate guardrail against infinite self-calls eating the C stack. Genuine depth (a real 3,000-deep chain) and accidental infinity (a missing base case, two functions calling each other forever) crash identically, which is why teams misdiagnose: they raise the limit for a bug, or hunt a bug in legitimately deep data.

You'll learn to read the repeating-frame signature that separates missing base cases from mutual recursion, why setrecursionlimit is a segfault-flavored trap, and the iterative rewrites — explicit stacks, loops, trampolines of thought — that handle arbitrary depth safely. By the end, recursion will be a tool you use for shallow trees and replace on sight for depth-proportional data.

The 1000-Frame Guardrail: What the Limit Protects

sys.getrecursionlimit() returns 1000 on stock Python — the maximum Python call frames allowed before RecursionError. Each recursive call pushes a frame holding locals, the return address, and evaluation state; 1000 such frames is Python's way of saying 'this looks infinite, stop before the C stack underneath overflows'. The C stack (typically 8 MB per thread) can't grow on demand, so an unbounded Python recursion would corrupt the interpreter rather than merely exhaust memory.

Depth counts frames, not calls over time: a function that recurses 10 deep a million times sequentially never exceeds 10 frames, while one 1,001-deep chain raises on the first traversal. That distinction focuses every diagnosis — the question is always maximum simultaneous depth, never total calls. Print the limit, print your measured depth, and compare the two numbers before theorizing further.

Respect the guardrail's purpose when tempted to move it. Raising the limit to 2000 for a legitimately 1,500-deep structure can be reasonable with testing; raising it to 100000 to silence a missing base case converts a catchable Python exception into a C-level segfault that kills the worker with no traceback. The limit is a smoke detector — relocating it doesn't put out the fire.

import sys

print("limit:", sys.getrecursionlimit())

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

print("depth 100 ok:", depth_probe(100))
try:
    depth_probe(2000)  # exceeds the 1000-frame guardrail
    print("unexpectedly survived")
except RecursionError as exc:
    print("raised as designed", type(exc).__name__ + ":", exc)

Missing Base Case: The Off Switch You Forgot

Every recursive function needs a base case — an input branch that returns without recursing — or every input recurses forever. The classic failure drops the base during a refactor: factorial keeps if n == 0: return 1 in the original, then someone 'simplifies' the helper and the n == 0 branch now calls factorial(-1) instead. Negative inputs march away from the base forever, and even valid inputs fail if the step moves the wrong direction.

Diagnose by reading the traceback's repeating frame: it names the function and the line of the recursive call. Then check three things in order — does a base branch exist, does the step move toward it for all inputs (including 0 and negatives), and does the recursive call pass the reduced value rather than the original. One 'no' among the three is the whole bug.

Harden with input validation at the entry: reject negatives for factorial-like functions with ValueError, clamp or handle 0 explicitly, and add tests for 0, 1, and a negative. The 2-node category cycle was a missing base case of a subtler kind — no 'already seen' branch — but the reading method is identical: repeating frames name the loop, and the absent branch is the fix.

Cover 0, negatives, and repeats in one parametrized test so the three cheapest inputs guard the most expensive failure.

def factorial(n):
    if n < 0:
        raise ValueError(f"factorial needs n >= 0, got {n}")
    if n <= 1:  # base case: the off switch
        return 1
    return n * factorial(n - 1)

print(factorial(0), factorial(5))
try:
    factorial(-3)
except ValueError as exc:
    print("guarded:", exc)

def walk(chain, seen=None):
    seen = seen if seen is not None else set()
    if chain is None or chain in seen:  # base cases: end + cycle
        return []
    seen.add(chain)
    return [chain] + walk({"next": None}.get("next"), seen)

print("cycle-safe walk:", walk("a"))

Mutual Recursion: Two Functions Bouncing Forever

Mutual recursion hides the loop across two or more functions: parse_item calls parse_list, which calls parse_item, with the handoff dropping the termination condition. Each function looks correct alone — the base case exists in one of them but the other never routes to it for some input shape. The traceback signature is unmistakable: two frame pairs alternating A, B, A, B for hundreds of repetitions instead of one function repeating.

Even/odd-style textbook examples work because numbers shrink toward zero on every handoff. Production versions break when one direction grows or stalls: a descent that re-adds the node, a parser that retries without consuming input, a state machine whose 'else' transitions back instead of forward. Any handoff that doesn't strictly shrink the problem can bounce forever on the right input.

Fix at the handoff: ensure every cross-call reduces a visible measure (remaining input length, unvisited count, depth budget), and add a shared visited set or remaining-budget parameter both functions honor. When the bounce involves callbacks or plugins you don't control, wrap the entry with a depth budget that raises a domain error past N handoffs — a loud, attributable failure beats 1000 silent frames.

def is_even(n, _seen=None):
    _seen = set() if _seen is None else _seen
    if n == 0:
        return True
    if n in _seen:  # cycle budget: no input should revisit a value
        raise ValueError(f"cycle detected at {n}")
    _seen.add(n)
    return is_odd(n - 1, _seen)

def is_odd(n, _seen=None):
    _seen = set() if _seen is None else _seen
    if n == 0:
        return False
    if n in _seen:
        raise ValueError(f"cycle detected at {n}")
    _seen.add(n)
    return is_even(n - 1, _seen)

print(is_even(10), is_odd(7))
print("alternating frames, shared seen-set, shrinking n: terminates")

setrecursionlimit Risks: Trading an Exception for a Segfault

sys.setrecursionlimit raises the Python-level cap — it does not enlarge the C stack underneath. Each frame still consumes C-level state, so pushing the limit to 10000 or 100000 on a default 8 MB thread stack overruns C memory and segfaults the worker: no traceback, no exception handler, no graceful restart — the process dies instantly and the log ends mid-line. That failure mode is strictly worse than RecursionError in every production dimension.

There is exactly one legitimate use: proven-finite depth slightly above 1000 (say 1,500) on threads with enlarged stacks, set once at startup with a comment citing the measured maximum plus margin, and covered by a test asserting depth stays under the new cap. Everything else — 'temporary' bumps to survive a release, per-request adjustments, limits above ~5000 on stock stacks — is borrowing against a crash with no diagnostics.

If anyone proposes the bump, demand the depth measurement first. Under ~900 frames: fix the base case, because the data fits and the loop is the bug. Over ~900 with real data: rewrite iteratively. Only the narrow band of proven-finite 1,000-2,000 with stack headroom justifies the call — and even there, the iterative rewrite is usually less code than the risk justification memo.

import sys

print("default limit:", sys.getrecursionlimit())
print("raising the cap does not enlarge the 8 MB C stack;")
print("10k frames can segfault where 1k raises catchably.")

def measured_depth(node):  # iterative measure: safe at any depth
    depth, cur = 0, node
    while cur is not None:
        depth += 1
        cur = cur.get("parent")
    return depth

chain = None
for _ in range(2500):
    chain = {"parent": chain}
print("measured depth:", measured_depth(chain), "-> rewrite, don't raise")

Iterative Rewrite: Explicit Stacks Handle Any Depth

The universal fix for depth-proportional work is replacing the call stack with a heap list used as a stack. Push the start node, pop and process until empty, pushing children as you go. Depth becomes list length in megabytes of flexible heap rather than frames in 8 MB of rigid C stack — 100,000 levels run flat where 1,001 crashed. The traversal order stays identical with small care: push children reversed for the same left-to-right order as the recursive version.

For accumulations like factorial or tree sums, a plain loop suffices — no stack list needed. For graph walks, add the visited set to the iterative version from the start; the explicit loop makes the seen-check cheaper and clearer than threading it through recursive parameters. For breadcrumb-style ancestor chains, walk parent pointers in a while loop collecting names, then reverse.

Port mechanically: base cases become loop-skip or break conditions, the recursive call becomes a push, and post-call work (combining child results) moves to a second pass or an explicit (node, visited_flag) tuple protocol. Test the rewrite against the recursive version on shallow inputs for identical output, then run the 3,000-deep case that killed the original. The passing deep test is the receipt proving the class is closed.

def breadcrumbs_iter(start, parents):
    seen, chain, cur = set(), [], start
    while cur is not None and cur not in seen:
        seen.add(cur)
        chain.append(cur)
        cur = parents.get(cur)  # None ends; repeat ends (cycle-safe)
    return chain

parents = {3: 2, 2: 1, 1: None}
print(breadcrumbs_iter(3, parents))
loop = {"a": "b", "b": "a"}
print("cycle ends, no raise:", breadcrumbs_iter("a", loop))
print("depth 3000:", len(breadcrumbs_iter(3000, {i: i - 1 for i in range(1, 3001)} | {0: None})))

Cycles in Data: Enforce Acyclicity Where Links Are Written

Code fixes stop the bleeding; write-time constraints stop the wound. Any recursive walk over user-editable links — category parents, manager hierarchies, task dependencies — will eventually meet a cycle, because humans misclick and imports merge badly. A visited set keeps the reader alive, but the cycle still exists, still confuses other consumers, and still waits for the one reader someone forgot to harden.

Enforce at three layers. The database gets a trigger or check constraint rejecting parent updates that create cycles — 40 ms per write on a 48,000-row table is invisible next to a 34-minute outage. The admin form validates by previewing the breadcrumb before save and refusing cycles with a named-path message. The import pipeline quarantines rows whose parent chains loop instead of loading them.

Monitor the near-misses: log every visited-set break with both node IDs so repeated admin mistakes surface as a pattern, not isolated lines. Three logged breaks since the search fix each traced to one training gap — fixed with a tooltip, not an incident. Runtime guards plus write-time constraints plus near-miss logs turn a category of outage into a category of non-event.

Review the near-miss log monthly; repeated node pairs reveal the training gap or import bug feeding the cycles.

def would_cycle(child, new_parent, parents):
    cur = new_parent
    seen = set()
    while cur is not None and cur not in seen:
        if cur == child:
            return True
        seen.add(cur)
        cur = parents.get(cur)
    return False

parents = {"winter": "clearance", "clearance": None}
print("winter -> clearance ok:", would_cycle("sale", "winter", parents))
print("clearance -> winter cycles:", would_cycle("winter", "clearance", {"winter": None, "clearance": None}) or would_cycle("clearance", "winter", {"clearance": "winter", "winter": "clearance"}))
print("write-time check: reject the second save, keep the reader simple")