The error RecursionError: maximum recursion depth exceeded occurs when a recursive function calls itself too many times without reaching a base case, leading to a stack overflow.
1. What is Recursion in Python?
Recursion is when a function calls itself repeatedly to solve a problem. Every function call uses memory, so if recursion goes too deep, Python stops execution to prevent a crash.
Python sets a default recursion limit of 1,000 calls.
You can check this limit using:
import sys
print(sys.getrecursionlimit()) # Default is 1000
2. Common Causes and Solutions
Cause 1: Infinite Recursion (No Base Case)
If a recursive function never stops calling itself, it leads to infinite recursion.
Example (Infinite Recursion)
def infinite_recursion(n):
return infinite_recursion(n + 1) # No stopping condition
infinite_recursion(1)
Solution: Always define a base case (a stopping condition).
def safe_recursion(n):
if n == 0: # Base case
return 1
return safe_recursion(n - 1) + 1
safe_recursion(5) # Works fine
Cause 2: Recursion Depth Too High
Even with a base case, deep recursion can exceed the default limit.
Example (Deep Recursion)
def deep_recursion(n):
if n == 0:
return 1
return deep_recursion(n - 1)
deep_recursion(2000) # Exceeds the limit
Solution: Increase recursion depth limit ( Use with caution).
import sys
sys.setrecursionlimit(3000) # Increase recursion limit
deep_recursion(2000) # Now works
Warning: Increasing recursion depth too much can crash Python.
Cause 3: Using Recursion for Large Problems
Some problems require too many recursive calls (e.g., calculating Fibonacci numbers).
Example (Slow Fibonacci Function)
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(100)) # Takes too long, may exceed depth
Solution: Use Memoization (Caching) to store results.
from functools import lru_cache
@lru_cache(maxsize=None) # Cache results to avoid redundant calls
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(100)) # Fast execution
Cause 4: Using Recursion When Iteration is Better
Some problems can be solved with loops instead of recursion.
Example (Factorial Using Recursion)
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
factorial(1000) # Causes RecursionError
Solution: Use an iterative approach.
def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
factorial_iterative(1000) # No recursion error
3. Summary of Fixes
| Issue | Fix |
|---|---|
| Infinite recursion | Add a base case |
| Too many recursive calls | Use sys.setrecursionlimit() (carefully) |
| Inefficient recursive algorithms | Use memoization (@lru_cache) |
| Recursion not necessary | Use loops (iterative approach) |