RecursionError: maximum recursion depth exceeded in Python

Verified FixPython 3.10+Python NativeSilo: core

Quick Fix / Solution Rapide

This error occurs when a recursive function lacks a terminating base case or traverses deep data structures. Add a base case or rewrite using an explicit loop.

Root Cause Analysis

This error occurs when Python tries to execute recursive function calls that exceed the runtime call stack limit set by CPython's recursion depth limit.

Cause 1: Missing or Unreachable Base Cases

Every recursive algorithm requires a termination condition (base case). If a recursive call fails to decrement its parameters toward the base condition, the function calls itself indefinitely until hitting the stack limit and raising RecursionError: maximum recursion depth exceeded.

Cause 2: Deeply Nested Tree or Graph Structures

Parsing deep JSON structures, nested AST trees, or linked lists with more than 1,000 levels of depth naturally exhausts CPython's default stack limit (1,000 frames).

Cause 3: Recursive Magic Methods (repr, getattr, eq)

A common bug is writing def __repr__(self): return str(self) or accessing self.attribute inside __getattr__, causing infinite self-referential recursion.

Cause 4: Lack of Tail Call Optimization (TCO) in Python

Unlike some functional languages, Python deliberately does not perform Tail Call Optimization to preserve full stack trace visibility for debugging.

Reproduction Code (MCVE)

Example: Bug Reproduction

def calculate_total(n):
    # Missing base case: recursion never terminates
    return n + calculate_total(n - 1)

calculate_total(10)

Solution 1: Add Explicit Base Conditions to Recursive Functions

Provide a clear termination guard at the top of the recursive function to halt recursion when target bounds are reached.

Example: Recommended Solution

def calculate_total(n):
    # Explicit base case
    if n <= 1:
        return n
    return n + calculate_total(n - 1)

result = calculate_total(10)
print(f'Recursive total: {result}')

Solution 2: Rewrite Iteratively Using an Explicit Loop or Stack

Convert deep recursive algorithms into iterative while/for loops with explicit collections (list/deque), which operate on heap memory without stack limits.

Example: Alternative Solution

def calculate_total_iterative(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

result = calculate_total_iterative(10)
print(f'Iterative total: {result}')

Common Mistakes & Edge Cases

1. sys.setrecursionlimit() Risks

While sys.setrecursionlimit(5000) increases the limit, setting it excessively high can trigger hard segmentation faults and crash the CPython interpreter when the C call stack overflows OS memory.

2. Contrasting RecursionError vs Infinite While Loops

RecursionError: Occurs exclusively during function calls when stack frames exceed the recursion limit.
Infinite While Loop (while True:): Continues executing indefinitely consuming CPU without allocating stack frames and does not raise RecursionError.

3. Memoization with functools.lru_cache

For recursive algorithms with overlapping subproblems (e.g. Fibonacci), applying @functools.lru_cache reduces time complexity from exponential to linear, preventing redundant recursive depth.

Previous Next