How to Fix Python RecursionError and Stack Overflow

TL;DR

• Bottom line: Python's default recursion limit is 1000 calls. RecursionError: maximum recursion depth exceeded means your code either has no base case, has an unreachable base case, or legitimately needs deeper recursion. Fix the base case first; convert to iterative with an explicit stack for deep recursion; use sys.setrecursionlimit() only as a temporary measure.
• Key tool/command: sys.setrecursionlimit(N) to raise the limit temporarily; convert to iterative with stack = [initial]; while stack: item = stack.pop() for a permanent fix.
• Watch out for: Blindly raising the limit with sys.setrecursionlimit(10**6) without increasing the OS thread stack size -- this causes a segfault instead of a clean Python exception.
• Works with: All CPython versions 2.7+/3.x. Behavior changed in 3.12+ (C stack limit is now separate and hardcoded). PyPy has a different default limit (~1000 but measured differently).

Constraints

• Default limit is 1000: CPython sets sys.getrecursionlimit() to 1000. This includes all nested Python function calls, not just the recursive function itself. Framework overhead (Django, Flask) may consume 50-100 frames before your code runs. [src1]
• Python 3.12+ split the limit: sys.setrecursionlimit() only controls Python-level recursion. C-level recursion is governed by Py_C_RECURSION_LIMIT, which is hardcoded. [src7]
• No tail-call optimization in CPython: Tail-recursive functions are NOT optimized. Every recursive call adds a new frame. [src4]
• Segfault risk above OS stack size: Each Python frame uses ~1-2 KB of C stack. With typical 8 MB thread stack, max is ~4000-8000 frames. Setting sys.setrecursionlimit(100000) without increasing OS stack size causes segfault. [src1, src3]
• resource module is Unix-only: resource.setrlimit(resource.RLIMIT_STACK, ...) is not available on Windows. Use threading.stack_size() for new threads instead. [src1]

Quick Reference

Decision Tree

START
├── Does the traceback show the SAME function repeating?
│   ├── YES -- Is there a base case (if/return without recursing)?
│   │   ├── NO -> Add a base case. See Step 1.
│   │   └── YES -> Is the base case reachable? Add print(args) to check.
│   │       ├── NO -> Fix the condition. See Step 2.
│   │       └── YES -> Recursion is legitimately deep (continue below)
│   └── NO -- Do TWO functions alternate in the traceback?
│       ├── YES -> Mutual recursion. Break the cycle. See Step 3.
│       └── NO -> Check for __repr__/__str__/__eq__ in traceback
├── Does traceback mention __repr__, __str__, __eq__, or property?
│   ├── YES -> Accidental self-reference in dunder method. See Anti-Pattern #4.
│   └── NO (continue below)
├── Is recursion depth < 1000 but still failing?
│   ├── YES -> Framework overhead consuming frames. Increase limit by 500-1000.
│   └── NO (continue below)
├── Do you need depth > 10000?
│   ├── YES -> MUST convert to iterative with explicit stack. See Step 5.
│   └── NO (continue below)
├── Do you need depth 1000-10000?
│   ├── YES -> Option A: sys.setrecursionlimit(N+100). Option B: Convert to iterative.
│   │   └── If setting limit: also increase OS stack size or run in a new thread.
│   └── NO (continue below)
└── DEFAULT -> Check for accidental recursion (property calling itself, __init__ calling __init__).

Step-by-Step Guide

1. Identify the missing or broken base case

Most RecursionErrors are caused by a missing or unreachable base case. Read the traceback to find the repeating function call and verify its termination condition. [src4]

# Example: broken base case -- never reaches 0 for negative input
def factorial(n):
    if n == 0:       # Bug: what if n < 0?
        return 1
    return n * factorial(n - 1)

# factorial(-1) -> RecursionError

# FIXED: handle edge cases
def factorial(n):
    if n < 0:
        raise ValueError(f"factorial not defined for negative: {n}")
    if n <= 1:       # Covers 0 and 1
        return 1
    return n * factorial(n - 1)

Verify: factorial(0) returns 1, factorial(-1) raises ValueError, factorial(10) returns 3628800.

2. Debug the base case with argument tracing

When the base case exists but is never reached, log the arguments at each recursive call. [src4]

import sys

def find_path(graph, start, end, path=None):
    if path is None:
        path = []
    path = path + [start]
    if start == end:
        return path
    for node in graph.get(start, []):
        if node not in path:  # Prevents infinite loops in cyclic graphs
            result = find_path(graph, node, end, path)
            if result:
                return result
    return None

Verify: Tracing output shows why the base case is not reached.

3. Break mutual recursion cycles

When function A calls B and B calls A without termination. [src4]

# FIXED: guard against negative input
def is_even(n):
    n = abs(n)
    if n == 0:
        return True
    return is_odd(n - 1)

def is_odd(n):
    n = abs(n)
    if n == 0:
        return False
    return is_even(n - 1)

Verify: is_even(-4) returns True, is_odd(3) returns True.

4. Apply memoization to reduce effective depth

For problems like Fibonacci where the same subproblems recur, @lru_cache reduces actual recursion depth dramatically. [src5]

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

# Warm up cache incrementally to avoid deep first call
def fib_safe(n):
    chunk = 500
    for target in range(chunk, n + 1, chunk):
        fib(target)
    return fib(n)

print(fib_safe(10000))  # Works

Verify: fib_safe(10000) completes without RecursionError.

5. Convert to iterative with an explicit stack

The universal fix for deep recursion. Replace the call stack with a list. [src6]

# ITERATIVE -- handles any depth, uses O(n) heap memory
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in reversed(graph.get(node, [])):
            if neighbor not in visited:
                stack.append(neighbor)
    return visited

Verify: Iterative version handles graphs with 100K+ nodes.

6. Raise the limit safely (temporary measure)

When you cannot refactor immediately and know the required depth. [src1]

import sys
import threading

# Option A: Raise limit (risk of segfault if too high)
sys.setrecursionlimit(5000)

# Option B: Run deep recursion in a thread with larger stack
def run_deep_recursion():
    sys.setrecursionlimit(50000)
    result = deep_recursive_function(30000)
    return result

# Set thread stack size to 64 MB
threading.stack_size(67108864)  # 64 * 1024 * 1024
thread = threading.Thread(target=run_deep_recursion)
thread.start()
thread.join()

Verify: sys.getrecursionlimit() returns the new value.

7. Use the trampoline pattern for tail-recursive functions

When you have a naturally tail-recursive function and want to avoid stack growth. [src4, src6]

def trampoline(fn):
    def wrapper(*args, **kwargs):
        result = fn(*args, **kwargs)
        while callable(result):
            result = result()
        return result
    return wrapper

@trampoline
def factorial_tr(n, acc=1):
    if n <= 1:
        return acc
    return lambda: factorial_tr(n - 1, n * acc)

print(factorial_tr(50000))  # Works -- constant stack depth

Verify: factorial_tr(50000) completes without RecursionError.

Code Examples

Python: Iterative tree traversal (in-order)

# Input:  Binary tree root node
# Output: List of values in in-order traversal

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_iterative(root):
    result, stack = [], []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

Python: Iterative flood fill

# Input:  2D grid, start position, new color
# Output: Grid with connected region recolored

def flood_fill(image, sr, sc, new_color):
    rows, cols = len(image), len(image[0])
    old_color = image[sr][sc]
    if old_color == new_color:
        return image
    stack = [(sr, sc)]
    while stack:
        r, c = stack.pop()
        if (0 <= r < rows and 0 <= c < cols
                and image[r][c] == old_color):
            image[r][c] = new_color
            stack.extend([(r+1,c),(r-1,c),(r,c+1),(r,c-1)])
    return image

Python: Recursive-to-iterative general pattern

# Input:  Any recursive function
# Output: Equivalent iterative with explicit stack

def flatten_nested(data):
    """Flatten arbitrarily nested lists -- iterative."""
    result = []
    stack = [iter(data)]
    while stack:
        try:
            item = next(stack[-1])
            if isinstance(item, list):
                stack.append(iter(item))
            else:
                result.append(item)
        except StopIteration:
            stack.pop()
    return result

# flatten_nested([1, [2, [3, 4], 5], 6]) -> [1, 2, 3, 4, 5, 6]

Anti-Patterns

Wrong: Blindly raising the recursion limit

# BAD -- causes segfault instead of clean RecursionError [src1, src3]
import sys
sys.setrecursionlimit(10**6)

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

deep(500000)  # Segmentation fault (core dumped)

Correct: Convert to iterative or raise limit with matching stack size

# GOOD -- iterative version with no stack limit [src6]
def deep(n):
    result = 0
    for _ in range(n):
        result += 1
    return result

deep(500000)  # Works instantly

Wrong: Using recursion for linear iteration

# BAD -- recursion where a simple loop suffices [src4]
def sum_list(lst, index=0):
    if index >= len(lst):
        return 0
    return lst[index] + sum_list(lst, index + 1)

sum_list(range(2000))  # RecursionError

Correct: Use a loop for linear iteration

# GOOD -- natural loop, no recursion overhead [src4]
def sum_list(lst):
    return sum(lst)  # Built-in, C-optimized

Wrong: Property getter that references itself

# BAD -- self.name triggers the getter recursively [src2]
class User:
    def __init__(self, name):
        self.name = name

    @property
    def name(self):
        return self.name  # Infinite recursion!

    @name.setter
    def name(self, value):
        self.name = value  # Infinite recursion!

Correct: Use a private backing attribute

# GOOD -- separate backing attribute [src2]
class User:
    def __init__(self, name):
        self.name = name

    @property
    def name(self):
        return self._name

    @name.setter
    def name(self, value):
        self._name = value

Wrong: Recursive __repr__ on circular references

# BAD -- circular reference causes infinite repr [src2]
class Node:
    def __init__(self, val, neighbors=None):
        self.val = val
        self.neighbors = neighbors or []

    def __repr__(self):
        return f"Node({self.val}, neighbors={self.neighbors})"

a, b = Node(1), Node(2)
a.neighbors.append(b)
b.neighbors.append(a)
print(a)  # RecursionError

Correct: Limit repr depth or show only IDs

# GOOD -- repr does not recurse into neighbors [src2]
class Node:
    def __init__(self, val, neighbors=None):
        self.val = val
        self.neighbors = neighbors or []

    def __repr__(self):
        neighbor_ids = [n.val for n in self.neighbors]
        return f"Node({self.val}, neighbors={neighbor_ids})"

Common Pitfalls

• Framework frames eat into the limit: Django, Flask, and FastAPI add 30-80 frames before your handler runs. Set the limit 200+ above your actual need. [src1]
• @lru_cache does not prevent deep recursion: Memoization reduces redundant calls but the first cold call to fib(2000) still recurses 2000 deep. Warm up incrementally. [src5]
• sys.setrecursionlimit affects all threads: The limit is process-wide. Prefer running deep recursion in a dedicated thread with threading.stack_size() set appropriately. [src1]
• Catching RecursionError and continuing is unreliable: After RecursionError, very little stack space remains. Keep handlers minimal. [src2]
• sys.setrecursionlimit changed in Python 3.12: Since 3.12, only controls Python frames. C-level recursion has a separate hardcoded limit. [src7]
• Generators with yield from create frame chains: yield from recursive_generator() creates generator frames that count toward the limit. Use iterative generators for deep data. [src4]
• PyPy has different limits: PyPy frames are lighter -- the same limit value allows deeper effective recursion than CPython. Do not assume identical behavior. [src1]
• Multiprocessing forks reset the limit: Child processes start with default 1000 unless explicitly set again. [src1]

Diagnostic Commands

# Check current recursion limit
python -c "import sys; print(sys.getrecursionlimit())"

# Check OS thread stack size (Linux/macOS)
ulimit -s

# Find safe maximum recursion depth for your system
python -c "
import sys
sys.setrecursionlimit(100000)
def probe(n):
    try:
        if n == 0: return 0
        return probe(n - 1)
    except RecursionError:
        return n
print(f'Max safe depth: ~{probe(99999)}')
"

# Check if resource module is available (Unix only)
python -c "
try:
    import resource
    soft, hard = resource.getrlimit(resource.RLIMIT_STACK)
    print(f'Stack limit: soft={soft}, hard={hard}')
except ImportError:
    print('resource module not available (Windows)')
"

Version History & Compatibility

When to Use / When Not to Use

Important Caveats

• On Python 3.12+, sys.setrecursionlimit() and the C stack recursion limit are decoupled. Raising the Python limit does not prevent C-level stack overflow.
• Setting a very high recursion limit without increasing OS thread stack size causes a segmentation fault -- an unrecoverable crash with no Python traceback.
• RecursionError was introduced in Python 3.5. Code catching RuntimeError to handle recursion may inadvertently catch unrelated errors.
• The trampoline pattern eliminates stack growth but adds per-call overhead from the wrapper loop. For performance-critical code, direct iterative rewrite is faster.
• Python's re module uses C-level recursion for regex matching. Complex patterns on long strings can hit the C recursion limit independently.
• In asyncio, recursive async functions consume coroutine frames that count toward the recursion limit.