PYTHON / FUNCTIONS
Recursion and the recursion limit
Write recursive functions with a correct base case, reason about call-stack depth, and know when CPython's 1000-frame limit means you need a loop.
What you will learn
- Give every recursive function a base case reached by strictly shrinking input
- Each unfinished call holds one stack frame: the limit caps depth, not total calls
- Read RecursionError as a missing base case or a too-deep design, not a Python quirk
- Prefer a loop or an explicit stack over raising sys.setrecursionlimit
Understanding Recursion and the recursion limit
A recursive call is an ordinary function call that happens to target the function already running. Nothing special happens to the variables: each call gets a fresh frame with its own copy of the parameters, so the `n` inside `total(3)` is unrelated to the `n` inside `total(2)`. The frames pile up while calls are still waiting for an answer, and they are popped in reverse order as each `return` fires. That pile is why a recursive function needs a base case: some input for which it returns without calling itself, so the unwinding can start.
CPython counts how many Python frames are currently stacked and refuses to push more than `sys.getrecursionlimit()`, which is 1000 by default. Exceeding it raises `RecursionError` instead of letting the process crash, because the real constraint underneath is the operating system's fixed stack size for the interpreter, which Python cannot grow on demand. Note also that CPython does not optimise tail calls: writing `return helper(n - 1)` as the last statement still costs a frame, so depth is always real depth, never folded into a loop for you.
So recursion is a good fit when the *data* is nested and shallow relative to its size, and a poor fit when depth grows with the number of items. Walking a parsed JSON document, a directory tree, or a binary search tree nests a few dozen levels for millions of nodes. Summing a 100,000-element list recursively nests 100,000 levels and dies at frame 1000. When you hit that wall, rewrite the traversal as a loop with an explicit list used as a stack; that moves the pending work onto the heap, which has no 1000-item ceiling.
import sys
def total(n):
if n == 0: # base case: nothing left to add
return 0
return n + total(n - 1) # recursive case: strictly smaller n
def runaway(n):
return runaway(n + 1) # no base case at all
print(total(10))
print(sys.getrecursionlimit())
print(total(900))
try:
runaway(0)
except RecursionError as exc:
print(type(exc).__name__)
try:
total(5000)
except RecursionError:
print("total(5000) needs ~5000 frames")Recursion is bounded by depth, the number of calls still waiting to return, not by how many calls happen in total.
Worked examples
Seeing the stack grow and shrink
Printing an indent per level makes the call tree visible and shows that depth and call count are different numbers.
def fib(n, depth=0):
print(" " * depth + f"fib({n})")
if n < 2:
return n
return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)
print(fib(4))Example explained
Line 1`depth` is threaded through the calls only to control the indent; it plays no part in the maths.
Line 2Nine lines are printed, so nine calls ran, but the deepest indent is 3, so at most 4 frames existed at once.
Line 3`fib(1)` and `fib(0)` are the base cases: they return without calling `fib` again, which lets the stack unwind.
Line 4`fib(2)` appears twice at different indents because this shape re-solves subproblems; that costs time, not stack depth.
Linear recursion versus a loop
Counting a 5000-element list recursively needs 5000 frames and fails, while the loop version has no depth cost at all.
import sys
def rec_len(items):
if not items:
return 0
return 1 + rec_len(items[1:])
def loop_len(items):
n = 0
for _ in items:
n += 1
return n
data = list(range(5000))
print(loop_len(data))
try:
rec_len(data)
except RecursionError as exc:
print("recursive version:", type(exc).__name__)
sys.setrecursionlimit(6000)
print(rec_len(data))Example explained
Line 1`items[1:]` builds a new list on every call, so `rec_len` is quadratic in copying as well as 5000 frames deep.
Line 2`loop_len` keeps one frame no matter how long the list is, which is why iteration is the right tool for flat data.
Line 3`sys.setrecursionlimit(6000)` makes the recursive call succeed, but it only moves the wall; a 50,000-element list would need another bump.
Line 4Raising the limit far above a few thousand risks a hard interpreter crash, because the OS stack size is unaffected by that call.
Recursion that fits the data
Flattening a nested list recurses only as deep as the nesting, so the frame count stays tiny even for many elements.
def flatten(item):
if not isinstance(item, list):
return [item] # base case: a plain value
result = []
for sub in item:
result.extend(flatten(sub))
return result
nested = [1, [2, [3, [4, 5]], 6], [[7]]]
print(flatten(nested))
print(flatten(42))Example explained
Line 1The base case is a type test, not a size test: anything that is not a list is already flat.
Line 2The `for` loop handles breadth and the recursive call handles depth, so the two mechanisms do not compete.
Line 3Maximum depth here is 4, matching the deepest bracket nesting, not the 7 values, so the 1000-frame limit is irrelevant.
Line 4`flatten(42)` shows the base case working on its own, which is the quickest way to check a recursive function.
Important notes
The limit counts all Python frames on the stack, not just recursive ones, so code already 50 frames deep inside a web framework or test runner has 50 fewer to spend.
RecursionError subclasses RuntimeError, and catching it leaves whatever the recursion was building half-finished; treat it as a bug report about your design rather than as control flow.
Common mistakes
Recursing on the unchanged argument, like `return n + total(n)` instead of `total(n - 1)`: the input never reaches the base case and you get RecursionError after about 1000 frames rather than an infinite hang.
Calling the function recursively without returning it, e.g. `total(n - 1)` on its own line: the recursion runs correctly and then the function returns None, producing a confusing TypeError higher up.
Calling sys.setrecursionlimit(1000000) to make an error go away: Python stops counting but the operating system stack still has a fixed size, so the process can segfault with no traceback at all.
Try it yourself
Change, predict, then run
Write a recursive `depth(x)` that returns the nesting depth of a list, so `depth([1, [2, [3]]])` is 3 and `depth(7)` is 0. Then build a 2000-level nested list with `x = 0` followed by a loop of `x = [x]`, and confirm that `depth(x)` raises RecursionError under the default limit.
Open the Python workspaceCheck your understanding
A recursive function makes 100,000 calls in total but never has more than 12 calls waiting at once. Under the default recursion limit, what happens?
- It runs fine, because the limit caps how many frames are on the stack simultaneously, not how many calls occur
- It raises RecursionError, because Python counts every call a function makes to itself during the run
- It runs only if you first call sys.setrecursionlimit(100000) to allow that many calls
- It raises RecursionError only when the recursive calls happen inside a loop
Show answer
Each frame is popped as soon as that call returns, so the interpreter compares the current stack depth (12 here) against the limit. Option 2 confuses total calls with concurrent depth: `fib(25)` written naively makes over 240,000 calls yet never exceeds depth 25, and it runs without any adjustment to the limit.