RecursionError: maximum recursion depth exceeded
ID: python/recursion-limit-exceeded
Version Compatibility
| Version | Status | Introduced | Deprecated | Notes |
|---|---|---|---|---|
| 311 | active | — | — | — |
Root Cause
Almost always resolvable by refactoring the recursive algorithm to iterative form or adding proper memoization. The error indicates genuine infinite or excessively deep recursion; increasing the limit merely delays the crash and risks a segfault from stack overflow.
genericWorkarounds
-
91% success Convert recursive algorithm to iterative form using an explicit stack
Replace the recursive function with a while loop and a list used as a stack. For tree traversal: use 'stack = [root]; while stack: node = stack.pop(); stack.extend(node.children)'. For DFS/BFS, this is a standard transformation that eliminates recursion entirely.
Sources: https://docs.python.org/3/tutorial/datastructures.html#using-lists-as-stacks
-
78% success Add memoization with functools.lru_cache or functools.cache
Decorate the recursive function with @functools.lru_cache(maxsize=None) or @functools.cache (Python 3.9+). This caches previously computed results, converting exponential recursion (e.g., naive Fibonacci) to linear depth. Ensure function arguments are hashable.
Sources: https://docs.python.org/3/library/functools.html#functools.lru_cache
-
65% success Use tail-call optimization via trampolining
Refactor the function to return a thunk (zero-argument lambda) instead of making the recursive call directly. A trampoline loop repeatedly calls the thunk until a final value is returned. Libraries like 'tail-recursive' on PyPI automate this pattern.
Dead Ends
Common approaches that don't work:
-
Setting sys.setrecursionlimit(999999) or higher
85% fail
CPython uses the C stack for Python function calls. Raising the recursion limit beyond the OS thread stack size (typically 8MB on Linux, ~8000-10000 frames) causes a hard segfault instead of a catchable RecursionError. The limit exists as a safety mechanism. Setting it to 999999 will crash the process with SIGSEGV for any recursion deeper than ~8000 frames.
-
Increasing thread stack size with 'ulimit -s unlimited' or threading.stack_size()
70% fail
While this technically allows deeper recursion, it does not fix the underlying algorithmic problem. Algorithms that hit the recursion limit on realistic inputs (trees, graphs, parsing) will eventually exhaust any finite stack. It also consumes significantly more memory per thread and can cause OOM on multi-threaded applications.