When a function calls itself too many times without a proper exit condition, it leads to stack overflow, causing the error:
RecursionError: maximum recursion depth exceeded
1. Causes of Deep Recursion & Stack Overflow
- No Base Case in Recursive Functions
- A recursive function must have an exit condition to stop calling itself.
- Too Many Recursive Calls
- Python has a default recursion depth limit (usually 1000 calls).
- Exceeding this limit results in stack overflow.
- Large Recursive Calculations
- If recursion is used instead of iteration, it consumes too much memory.
- Mutual Recursion (Indirect Recursion)
- Two or more functions call each other indefinitely.
- Uncontrolled Tree Recursion
- When a function calls itself multiple times per recursion step.
2. How to Fix Deep Recursion?
Solution 1: Use an Explicit Base Case
A base case stops infinite recursion.
Bad Example (No Base Case)
def infinite_recursion():
return infinite_recursion() # Never stops, crashes after ~1000 calls
infinite_recursion()
Good Example (With Base Case)
def count_down(n):
if n <= 0: # Base case to stop recursion
return "Done"
return count_down(n - 1)
print(count_down(10)) # Works fine
Solution 2: Increase the Recursion Limit (Use with Caution!)
Python limits recursion depth to prevent crashes. You can increase it, but this risks memory overflow.
import sys
sys.setrecursionlimit(5000) # Increase recursion depth limit
⚠ Warning: Only increase if you’re sure your recursion is well-controlled!
Solution 3: Convert Recursion to Iteration
For large computations, use loops instead of recursion.
Bad Example (Recursive Fibonacci)
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(30)) # Slow and deep recursion
Good Example (Iterative Fibonacci)
def fibonacci_iterative(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fibonacci_iterative(30)) # Faster and no recursion error
Solution 4: Use Tail Recursion (If Supported)
Python does not optimize tail recursion, but some compilers do.
def tail_recursive_factorial(n, acc=1):
if n == 0:
return acc
return tail_recursive_factorial(n - 1, n * acc)
print(tail_recursive_factorial(5)) # Works, but still limited by Python
Since Python does not optimize tail recursion, iteration is better.
Solution 5: Use functools.lru_cache to Optimize Repeated Recursive Calls
Memoization stores previous results to avoid redundant calculations.
Optimized Fibonacci Using Memoization
from functools import lru_cache
@lru_cache(maxsize=None) # Cache previous results
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(100)) # Much faster, avoids deep recursion issues
Solution 6: Use a Stack Instead of Recursion
Instead of recursive function calls, use a stack (LIFO).
Example: Factorial Without Recursion
def factorial(n):
stack = []
while n > 1:
stack.append(n)
n -= 1
result = 1
while stack:
result *= stack.pop()
return result
print(factorial(5)) # 120
3. Summary of Fixes
| Cause | Fix |
|---|---|
| No base case in recursion | Add a stopping condition |
| Too many recursive calls | Convert recursion to iteration |
| Recursion limit too low | Increase with sys.setrecursionlimit() (cautiously) |
| Inefficient calculations | Use @lru_cache to optimize |
| Tree recursion (e.g., Fibonacci) | Use loops or memoization |
| Mutual recursion | Refactor code to avoid indirect recursion |