Recursion depth limit — stack overflow — Coding notes

HOW it works step by step

Consider an infinite recursion (the classic bug):

def boom(n):
    return boom(n + 1)   # no base case → never stops
boom(0)

Worked example Tracing the stack growth

Call	Frame pushed	Depth
`boom(0)`	frame for n=0	1
`boom(1)`	frame for n=1	2
`boom(2)`	frame for n=2	3
...	...	...
`boom(999)`	frame for n=999	1000 → RecursionError

Why this step? Each call happens before the previous one returns, so no frame is ever popped. Depth climbs by 1 each call until it hits the limit.

Figure — Recursion depth limit — stack overflow

Inspecting and changing the limit

Formula Reading & setting the limit

$\text{depth at crash} \le \text{recursionlimit}$

import sys
sys.getrecursionlimit()      # → 1000 (default)
sys.setrecursionlimit(5000)  # raise it (carefully!)

Derivation of why it's not exactly 1000 in practice: the limit counts all frames, including the ones already on the stack when you start (the module, the REPL, etc.). So if $k$ frames already exist, your recursion can only go about $1000 - k$ deep. The bound is a total-frame count, not a per-function count.

Worked examples

Worked example Example 1 — Deep but legal recursion

def depth_sum(n):
    if n == 0:        # base case
        return 0
    return n + depth_sum(n - 1)
depth_sum(2000)       # RecursionError! default limit 1000

Why this step? depth_sum(2000) needs 2001 stacked frames at once — well past 1000. The logic is correct, but the depth exceeds the limit. Fix: either sys.setrecursionlimit(3000) or rewrite iteratively.

Worked example Example 2 — Iterative rewrite (no stack growth)

def depth_sum_iter(n):
    total = 0
    while n > 0:
        total += n
        n -= 1
    return total
depth_sum_iter(2_000_000)   # works fine, depth stays 1

Why this step? A loop reuses one frame; the variable total lives on the heap-friendly stack of one call. No frames pile up → no overflow regardless of n.

Worked example Example 3 — Catching the error

import sys
def safe_factorial(n):
    try:
        if n <= 1: return 1
        return n * safe_factorial(n - 1)
    except RecursionError:
        return None      # signal "too deep"

Why this step? RecursionError is a normal exception, so try/except works. This is why Python uses a soft limit instead of a segfault — you can recover.

The 80/20 takeaway

Flashcards

What data structure stores active function calls?

The call stack (LIFO), holding one stack frame per active call.

What is a stack frame made of?

The call's local variables, arguments, and return address (where to resume in the caller).

Define recursion depth.

The number of stack frames active (paused) at the same time during recursion.

What is the default recursion limit in CPython?

About 1000 total frames.

What error does Python raise on too-deep recursion?

RecursionError: maximum recursion depth exceeded.

Why does Python use a soft limit instead of crashing?

To raise a catchable RecursionError before the OS hits a hard, uncatchable stack overflow (segfault).

How do you read and change the limit?

sys.getrecursionlimit() and sys.setrecursionlimit(N).

Why is raising setrecursionlimit dangerous?

Too high a value can let recursion exhaust real stack memory, causing an uncatchable segfault.

Two robust fixes for hitting the limit?

Ensure a correct base case that's actually approached, or rewrite the algorithm iteratively.

Why does the limit not allow exactly 1000 of YOUR calls?

It counts all frames including pre-existing ones, so available depth ≈ 1000 − (already-stacked frames).

Recall Feynman: explain to a 12-year-old

Imagine you're stacking dinner plates. Every time a function calls itself, you put one more plate on the pile — that plate remembers what the function was doing. When the deepest function finishes, you take a plate off. But if a function keeps calling itself and never finishes, you keep stacking plates forever. Eventually the pile is too tall and would crash to the floor. Python is smart: at about 1000 plates it shouts "STOP! RecursionError!" instead of letting the whole thing topple. To really fix it, give the function a clear finish line (base case) it actually reaches — or use a simple loop that uses just one plate over and over.

Connections

Recursion — base case and recursive case
Iteration vs Recursion
Call stack and function frames
Exceptions and try-except in Python
Tail recursion and why Python lacks tail-call optimization
Memory model — stack vs heap

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, jab bhi ek function khud ko call karta hai (recursion), Python ko yaad rakhna padta hai ki "main kahan tha, kahan wapas aana hai". Yeh yaad-rakhne wala note ek stack frame hota hai, aur saare frames ek call stack pe plate ki tarah ek ke upar ek rakhe jaate hain. Har naya call = ek nayi plate upar. Agar function rukta hi nahi (base case galat ya missing hai), to plates badhti hi jaati hain.

Stack ki memory bahut chhoti aur fixed hoti hai, isliye CPython ek default limit ~1000 rakhta hai. Jaise hi depth 1000 cross karti hai, Python ek RecursionError throw kar deta hai — yeh ek soft limit hai taaki program seedha OS-level segfault se na mare. Matlab tum is error ko try/except se pakad bhi sakte ho, jo segfault me possible nahi tha.

Sabse common galti: log sochte hain "limit chhoti hai, chalo sys.setrecursionlimit ko 10 lakh kar dete hain." Yeh khatarnaak hai — agar tum real stack memory khatam kar do to uncatchable crash aa jaayega. Asli fix do hi hain: ya to base case sahi karo jo actually reach ho (har call base ke kareeb jaaye, jaise f(n-1)), ya phir algorithm ko loop (iteration) me likho jo sirf ek frame use karta hai chahe n 20 lakh ho.

Yaad rakhne ke liye: "No Base → Frames Race → Stack's out of Space." Bas itna samajh lo to recursion bug kabhi nahi haraega.

Recursion depth limit — stack overflow

WHAT is happening

WHY does a limit even exist

HOW it works step by step

Inspecting and changing the limit

Worked examples

The 80/20 takeaway

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Introduction to Programming (Python)

Connections