How to Fix Python RecursionError: maximum recursion depth

# How to Fix Python RecursionError: maximum recursion depth

The RecursionError: maximum recursion depth exceeded occurs when a recursive function calls itself too many times, exceeding Python's call stack limit. This typically indicates infinite recursion or a problem that needs an iterative solution.

Error Patterns

Basic RecursionError

Traceback (most recent call last):
  File "app.py", line 15, in <module>
    recursive_function(100)
  File "app.py", line 10, in recursive_function
    return recursive_function(n + 1)
  File "app.py", line 10, in recursive_function
    return recursive_function(n + 1)
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Infinite Recursion

Traceback (most recent call last):
  File "app.py", line 5, in factorial
    return n * factorial(n)
  [Previous line repeated 997 more times]
RecursionError: maximum recursion depth exceeded while calling a Python object

Deep Tree Traversal

Traceback (most recent call last):
  File "app.py", line 20, in traverse_tree
    traverse_tree(node.child)
  [Previous line repeated 998 more times]
RecursionError: maximum recursion depth exceeded

Comparison RecursionError

Traceback (most recent call last):
  File "app.py", line 25, in __eq__
    return self.value == other.value and self.children == other.children
RecursionError: maximum recursion depth exceeded in comparison

Common Causes

1. 1.Infinite recursion - Function calls itself without proper termination
2. 2.Missing base case - No condition to stop recursion
3. 3.Wrong recursion argument - Passing same or increasing value
4. 4.Circular references - Objects referencing each other recursively
5. 5.Deep data structures - Trees/lists deeper than stack limit
6. 6.Mutual recursion - Functions calling each other endlessly
7. 7.Default recursion limit too low - For legitimate deep recursion

Diagnosis Steps

Step 1: Check Current Recursion Limit

```python import sys

print(f"Current recursion limit: {sys.getrecursionlimit()}") print(f"Maximum recursion limit depends on system memory")

# Check usage import traceback # In your error, look at the repeated pattern to identify the loop ```

Step 2: Identify the Recursive Function

```python # Look at the traceback pattern # The error shows which function is being called repeatedly # Example: # File "app.py", line 10, in recursive_function # return recursive_function(n + 1) <- This is the problem

# Trace the calls manually def recursive_debug(n, depth=0): print(f"Call depth {depth}: n={n}") if depth > 10: print("Stopping debug after 10 calls") return # Your recursive logic here ```

Step 3: Check for Base Case

```python def analyze_recursion(func, args): """Simulate recursion to find issues.""" call_stack = [] current_args = args max_simulated = 100

for i in range(max_simulated): call_stack.append(current_args) # Try to simulate what the function does # This requires understanding the function logic print(f"Step {i}: args = {current_args}")

# Check if it should stop # if termination_condition(current_args): # print(f"Would terminate at step {i}") # break

print(f"After {max_simulated} steps, would exceed limit") ```

Solutions

Solution 1: Add Proper Base Case

```python # Problem: Missing base case causes infinite recursion def factorial(n): return n * factorial(n) # No base case, calls forever

# Fix: Add termination condition def factorial(n): if n <= 1: # Base case return 1 return n * factorial(n - 1) # Decreasing argument

# Test print(factorial(5)) # 120 ```

Solution 2: Fix Wrong Recursion Argument

```python # Problem: Argument doesn't decrease toward base case def countdown(n): print(n) if n > 0: countdown(n + 1) # WRONG: increases instead of decreases

# Fix: Decrease toward base case def countdown(n): print(n) if n > 0: countdown(n - 1) # Correct: decreases

# Another common mistake def sum_list(lst): if not lst: return 0 return lst[0] + sum_list(lst) # WRONG: same list passed

# Fix: Reduce the list def sum_list(lst): if not lst: return 0 return lst[0] + sum_list(lst[1:]) # Correct: slice list ```

Solution 3: Convert to Iterative Solution

```python # Problem: Deep recursion exceeds limit def fibonacci_recursive(n): if n <= 1: return n return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# fibonacci_recursive(1000) # RecursionError

# Fix: Use iterative approach def fibonacci_iterative(n): if n <= 1: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b

print(fibonacci_iterative(1000)) # Works fine

# Another example: factorial def factorial_iterative(n): result = 1 for i in range(2, n + 1): result *= i return result

print(factorial_iterative(100)) # Works fine ```

Solution 4: Increase Recursion Limit (Use Carefully)

```python import sys

# Check current limit print(sys.getrecursionlimit()) # Default is 1000

# Increase limit sys.setrecursionlimit(5000) # Be careful with this

# Now deep recursion works (but uses more memory) def deep_recursive(n, depth=0): if depth >= n: return depth return deep_recursive(n, depth + 1)

print(deep_recursive(4000)) # Works after increasing limit

# Warning: Increasing too much can cause stack overflow # Better to use iterative solutions for deep recursion ```

Solution 5: Fix Mutual Recursion

```python # Problem: Two functions calling each other endlessly def func_a(n): return func_b(n) # No termination

def func_b(n): return func_a(n) # No termination

# Fix: Add termination condition in one or both def func_a(n): if n <= 0: # Base case return 0 return func_b(n - 1)

def func_b(n): if n <= 0: # Base case return 0 return func_a(n - 1)

print(func_a(10)) # Works ```

Solution 6: Fix Circular Object References

```python # Problem: __eq__ or other methods cause recursion class Node: def __init__(self, value, children=None): self.value = value self.children = children or []

def __eq__(self, other): # Circular reference if children contain self return self.value == other.value and self.children == other.children

# Fix: Use explicit depth limit or track visited class Node: def __init__(self, value, children=None): self.value = value self.children = children or []

def __eq__(self, other, visited=None): if visited is None: visited = set()

# Prevent circular comparison if id(self) in visited or id(other) in visited: return True # Already compared

visited.add(id(self)) visited.add(id(other))

return self.value == other.value and \ len(self.children) == len(other.children) and \ all(c1 == c2 for c1, c2 in zip(self.children, other.children)) ```

Solution 7: Use Stack-Based Tree Traversal

```python # Problem: Deep tree exceeds recursion limit def traverse_recursive(node): process(node) for child in node.children: traverse_recursive(child) # Deep trees fail

# Fix: Use explicit stack def traverse_iterative(root): stack = [root] while stack: node = stack.pop() process(node) # Add children to stack (reverse for correct order) stack.extend(reversed(node.children))

# For BFS, use queue instead from collections import deque

def traverse_bfs(root): queue = deque([root]) while queue: node = queue.popleft() process(node) queue.extend(node.children) ```

Solution 8: Memoize to Reduce Recursive Calls

```python # Problem: Fibonacci recalculates same values many times def fib_slow(n): if n <= 1: return n return fib_slow(n - 1) + fib_slow(n - 2)

# fib_slow(50) # Takes forever, might hit recursion limit

# Fix: Use memoization from functools import lru_cache

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

print(fib_cached(100)) # Fast, no recursion limit issue

# Manual memoization def fib_memo(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo) return memo[n] ```

Common Recursion Patterns Fixed

List Processing

```python # Recursive (limited) def find_max_recursive(lst): if len(lst) == 1: return lst[0] return max(lst[0], find_max_recursive(lst[1:]))

# Iterative (unlimited) def find_max_iterative(lst): max_val = lst[0] for val in lst: if val > max_val: max_val = val return max_val ```

Binary Search

```python # Recursive def binary_search_recursive(arr, target, low, high): if low > high: return -1 mid = (low + high) // 2 if arr[mid] == target: return mid elif arr[mid] < target: return binary_search_recursive(arr, target, mid + 1, high) else: return binary_search_recursive(arr, target, low, mid - 1)

# Iterative def binary_search_iterative(arr, target): low, high = 0, len(arr) - 1 while low <= high: mid = (low + high) // 2 if arr[mid] == target: return mid elif arr[mid] < target: low = mid + 1 else: high = mid - 1 return -1 ```

Directory Traversal

```python # Recursive (might fail on deep paths) def scan_directory_recursive(path): import os for entry in os.listdir(path): full_path = os.path.join(path, entry) if os.path.isdir(full_path): scan_directory_recursive(full_path) else: process_file(full_path)

# Iterative using os.walk (handles any depth) def scan_directory_iterative(path): import os for root, dirs, files in os.walk(path): for file in files: process_file(os.path.join(root, file)) ```

Debugging Recursion

Visualize Call Stack

```python def recursive_with_trace(n, depth=0, max_depth=50): """Recursion with stack visualization.""" print(f"{' ' * depth}Enter: n={n}, depth={depth}")

if depth >= max_depth: print(f"{' ' * depth}Warning: approaching limit at depth {depth}") return n

if n <= 0: # Base case print(f"{' * depth}Base case reached") return 0

result = n + recursive_with_trace(n - 1, depth + 1, max_depth) print(f"{' ' * depth}Exit: returning {result}") return result

recursive_with_trace(5) ```

Track Call Count

```python def recursion_counter(func): """Decorator to count recursive calls.""" counter = {'calls': 0}

def wrapper(*args, **kwargs): counter['calls'] += 1 if counter['calls'] > 100: raise RecursionError(f"Too many calls: {counter['calls']}") return func(*args, **kwargs)

wrapper.counter = counter return wrapper

@recursion_counter def my_recursive(n): if n <= 0: return 0 return my_recursive(n - 1)

try: result = my_recursive(1000) print(f"Result: {result}, Calls: {my_recursive.counter['calls']}") except RecursionError as e: print(f"Error: {e}") ```

Prevention Tips

1. 1.Always include base case - Termination condition is mandatory
2. 2.Ensure argument decreases - Each call should move toward base case
3. 3.Prefer iteration for deep structures - Use loops instead of recursion
4. 4.Use memoization - Cache results to avoid redundant calls
5. 5.Set recursion limit carefully - Only if you know the depth is safe

```python # Good pattern: Well-designed recursion def safe_recursive(data, depth=0, max_depth=100): # Always have both base case and depth limit if depth >= max_depth: raise ValueError(f"Maximum depth {max_depth} exceeded")

if should_terminate(data): return base_result

return safe_recursive(process(data), depth + 1, max_depth) ```

Related Errors

• StackOverflow - C-level stack overflow (more severe)
• MemoryError - Out of memory during recursion
• TypeError - Function doesn't return value for recursion
• KeyboardInterrupt - Often needed to stop runaway recursion