Recursion has a depth limit. When the input nests deeper than the limit, you hit a RecursionError. The fixes are to raise the limit, go bottom-up, or manage your own stack.
About 3 min of reading
Handle a recursion that is too deep.
Catch a RecursionError.
Before you run it, say out loud what it will print. Then open the answer.
Iterative nested sum.
Before you run it, say out loud what it will print. Then open the answer.
Iterative tree size.
Before you run it, say out loud what it will print. Then open the answer.
Loop sum to 100000.
Before you run it, say out loud what it will print. Then open the answer.
Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.
Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.
The recursion limit stops runaway calls before the real stack crashes. Raising it trades safety for reach, not unlimited memory.
Any recursion can be rewritten with your own stack in a loop. That removes the depth limit at the cost of clearer code.
import sys
sys.setrecursionlimit(50)
def f(n):
if n == 0:
return 0
return f(n - 1)
try:
f(100)
except RecursionError:
print(sys.getrecursionlimit())A depth past the limit raises RecursionError. The limit is a guard, not free memory.
import sys
sys.setrecursionlimit(10000)
def f(n):
if n == 0:
return 0
return f(n - 1)
print(f(1000))Raising the limit lets deeper calls run. Too high and the real stack still crashes.
def total(a):
stack = list(a)
s = 0
while stack:
x = stack.pop()
if isinstance(x, list):
stack.extend(x)
else:
s += x
return s
print(total([1, [2, [3]]]))Push the work onto a list yourself. No call frames, so no depth limit.
def size(root):
stack = [root]
n = 0
while stack:
node = stack.pop()
if node is None:
continue
n += 1
stack.append(node.get("left"))
stack.append(node.get("right"))
return n
tree = {"v": 1, "left": {"v": 2}, "right": {"v": 3}}
print(size(tree))An explicit stack walks the tree with no recursion. The stack lives in memory.
import sys
print(sys.getrecursionlimit())The default limit is around a thousand. A linked chain longer than that breaks a recursive walk.
n, acc = 100000, 0
while n:
acc += n
n -= 1
print(acc)For a long flat count, a loop has no depth limit at all. That is the safe default.
import sys
sys.setrecursionlimit(2000)
from functools import lru_cache
@lru_cache(maxsize=None)
def f(n):
if n < 2:
return n
return f(n - 1) + f(n - 2)
print(f(500))A cache removes repeated work but not the depth of the first chain. Depth still counts.
def height(node):
if node is None:
return 0
return 1 + max(height(node.get("left")), height(node.get("right")))
tree = {"v": 2, "left": {"v": 1}, "right": {"v": 3}}
print(height(tree))A balanced tree has log depth, so recursion is safe. A skewed one has linear depth.
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.