Recursion Limit and Going Iterative
18 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Python allows only about 1000 nested calls. A correct recursive function can still fail when the input needs more. This lesson shows how to read that limit, when to raise it, and when to switch to a loop or an explicit stack.
Python stops at about 1000 calls
Recursion limit is the largest number of nested calls Python allows. It is 1000 by default. Going deeper raises RecursionError, even when the function is correct.
Python limits how deep calls can go, so a runaway function cannot use all memory. The limit is easy to read, and easy to hit.
import sys
def depth_sum(n): if n == 0: return 0 return n + depth_sum(n - 1)
print(sys.getrecursionlimit())print(depth_sum(500))try: depth_sum(5000)except RecursionError: print("5000 calls is too deep")Example 1 · Reading the error
def depth_sum(n): if n == 0: return 0 return n + depth_sum(n - 1)
try: depth_sum(5000)except RecursionError as error: print(type(error).__name__) print("maximum recursion depth" in str(error))RecursionError True
What this code does
- The exception is an ordinary one, so you can catch it and report a clear message.
- Catching it hides the cause. Use it to explain a problem, not to carry on silently.
The default limit is 1000. A correct function still fails when the input needs more calls than that.
Raising the limit with sys.setrecursionlimit
sys.setrecursionlimit(n) sets the recursion limit for the running program. It makes deeper calls legal, but each call still uses memory, so a very large value risks a crash.
If the depth is large but known, ask Python for more room. The call takes the new limit as a number.
import sys
sys.setrecursionlimit(10_000)
def depth_sum(n): if n == 0: return 0 return n + depth_sum(n - 1)
print(depth_sum(5000))Example 2 · Raise the limit for one job
import sys
def depth_sum(n): if n == 0: return 0 return n + depth_sum(n - 1)
old_limit = sys.getrecursionlimit()sys.setrecursionlimit(20_000)print(depth_sum(10_000))sys.setrecursionlimit(old_limit)print(sys.getrecursionlimit() == old_limit)50005000 True
What this code does
- Save the old limit, raise it, finish the job and restore it.
- The restore keeps the rest of the program on the safe default.
Do not set a huge number. Very deep recursion can crash the whole program, and the new limit applies to everything that runs after it.
Turn the recursion into a loop
Iterative solution is code that repeats work with a loop instead of calls to itself. It uses constant call-stack space and has no recursion limit.
A function that adds one number per call is a loop in disguise. Keep a running total in a variable instead of a waiting call.
def total_to(n): total = 0 for value in range(1, n + 1): total += value return total
print(total_to(100_000))Example 3 · Recursive against loop
def depth_sum(n): if n == 0: return 0 return n + depth_sum(n - 1)
def loop_sum(n): return sum(range(n + 1))
print(loop_sum(200_000))try: depth_sum(200_000)except RecursionError: print("recursion failed")20000100000 recursion failed
What this code does
- The loop version handles 200,000 with no setup.
- The recursive one needs 200,000 waiting calls and fails at the default limit.
The loop uses constant memory and has no depth limit. Python does not turn the last call of a function into a jump, so deep tail calls are not free.
An explicit stack for nested data
Explicit stack is a list you manage yourself to remember work still to do. It does what the call stack does for recursion, but its size is limited only by memory.
Nested data can be deeper than the limit. A plain list used as a stack walks it with no recursion at all.
def count_items(data): stack = [data] count = 0 while stack: current = stack.pop() for item in current: if isinstance(item, list): stack.append(item) else: count += 1 return count
print(count_items([1, [2, [3, 4]], 5]))Example 4 · Deeply nested data
def build(depth): data = [1] for _ in range(depth): data = [data] return data
def count_recursive(data): total = 0 for item in data: total += count_recursive(item) if isinstance(item, list) else 1 return total
def count_items(data): stack = [data] count = 0 while stack: for item in stack.pop(): if isinstance(item, list): stack.append(item) else: count += 1 return count
deep = build(5000)print(count_items(deep))try: count_recursive(deep)except RecursionError: print("recursive version failed")1 recursive version failed
What this code does
buildwraps a list 5000 times, far deeper than the limit.- The explicit stack finds the one value. The recursive version raises RecursionError.
stack holds the lists still to visit. pop() takes the newest one, just like the call stack would. Only the heap limits the depth.
Next step
Check your understanding
10 quick questions