Recursion depth limit — stack overflow: Worked examples

1.2.39 · D3 · Coding › Introduction to Programming (Python) › Recursion depth limit — stack overflow

Neeche di gayi picture dekho: yeh Example 1, countdown(3) ke exact function ko trace karti hai. Ise upar se neeche padho: har call ek kala plate neeche rakhta hai, aur jis pal base case countdown(0) fire hoti hai (woh red plate) — stack apni sabse zyada height par hota hai — chaar plates unchai. Upar ki dashed line ~1000-frame limit hai; yeh chhota sa example uske paas kahin nahi hai, lekin is page ka har crash is same picture ka hi grown version hai jo us line ke paar chala gaya.

Figure — Recursion depth limit — stack overflow

Hum baar baar is "plate pile" par wapas aayenge — yeh matrix ke har cell ke peeche ka mental model hai.

The scenario matrix

Har recursion problem inhi cells mein se kisi ek mein land karti hai. Neeche ke examples us cell ke saath labeled hain jo woh cover karta hai.

Cell	Situation	Outcome kya decide karta hai
A	Base case present aur reach hua, depth < limit	Theek chalta hai, ek value return karta hai
B	Base case sahi hai lekin depth > limit	`RecursionError` bhi tab jab logic sahi ho
C	Base case missing (infinite)	`RecursionError` jaldi, hamesha
D	Base case exist karta hai lekin kabhi approach nahi hota	`RecursionError` — woh chhupa hua bug
E	Zero / degenerate input (`n = 0`, empty list)	Seedha base ko hit karta hai, depth = 1
F	Negative / wrong-direction input	Base ko overshoot karta hai, bhaag jaata hai
G	Branching recursion (khud ko do baar call karta hai)	Depth ≠ calls ka number — depth sabse lamba path hai
H	Deep-but-finite kaam ke liye deliberately limit badhaya	Chalta hai, lekin hard segfault ka risk hai
I	Real-world word problem	Story → depth mein translate karo
J	Exam twist — exact frames count karo, off-by-one	`1000` total frames hain, per-function nahi
K	Mutual (co-)recursion — `is_even`↔`is_odd`	Do functions bounce karte hain; depth combined chain hai, ab bhi ek shared stack

Inme se ek idea sab mein thread ki tarah hai. Pehle ek symbol earn karo:

Formula Ek hi inequality jo matter karti hai

$d \leq recursionlimit - k$ jahan $d$ = peak depth (abhi define kiya) aur $k$ = frames jo tumhari recursion shuru hone se pehle se stack par hain (module, REPL, the caller).

Yeh form kyun? (derivation). Interpreter frames per function count nahi karta — woh ek shared stack par har live frame count karta hai. Apni recursion ka peak depth $d$ lo aur woh $k$ frames jodo jo pehle se wahan baithe hain: peak par kul live frames $= d + k$ . Interpreter RecursionError tab raise karta hai jis pal woh total configured recursionlimit se zyada ho jaata hai, yaani jis pal $d + k > recursionlimit$ . Safe rehne ka matlab hai $d + k \leq recursionlimit$ , aur dono taraf se $k$ ghatane par box milta hai: $d \leq recursionlimit - k$ . Ise cross karo aur crash; $- k$ ko ignore karo aur exam mein off-by-one mistakes karogey.

Cell A + E — base reach hua, aur degenerate input

Worked example Example 1 —

countdown jo khatam hota hai (Cells A, E)

def countdown(n):
    if n == 0:            # base case
        return "liftoff"
    return countdown(n - 1)
countdown(3)
countdown(0)              # degenerate input

Forecast: countdown(3) kitna deep stack karta hai? countdown(0) kya karta hai — kya yeh recurse bhi karta hai?

countdown(3) trace karo. Frames push hue: n=3, n=2, n=1, n=0 — bilkul wahi chaar plates is page ke upar figure mein hain (base plate n=0 red hai). Yeh step kyun? Har call 1 subtract karta hai, isliye hum strictly approach karte hain base ko — plates ulte order mein waapas utrengi jab har return fire hogi.
Peak depth count karo. Jis pal n=0 chalta hai, chaar frames alive hain → $d = 4 = n + 1$ . Yeh step kyun? Depth woh frames hain jo ek saath stacked hain; $n$ se $0$ tak ek linear chain ke liye woh $n + 1$ hai.
countdown(0). if n == 0 seedha fire hota hai, "liftoff" return karta hai, koi recursive call nahi. Yeh step kyun? Degenerate input base hi hai — sirf red plate exist karti hai, $d = 1$ , sabse chhota possible.

Verify: countdown(3) ke liye peak depth $= 3 + 1 = 4 \leq 1000$ . Theek chalta hai. countdown(0) 0 baar recurse karta hai.

Cell C — koi base case nahi (pure infinite)

Neeche ki figure ek hi plate-height axis par do runs overlay karti hai: healthy countdown (black, $d = 4$ tak uthta hai phir girta hai) versus boom (red, seedha dashed limit line se paar hamesha ke liye chadhta hai). Yeh akela picture is page ke har runaway ki shape hai — Cells C, D aur F sab woh red line trace karte hain.

Worked example Example 2 —

boom bina finish line ke (Cell C)

def boom(n):
    return boom(n + 1)   # kuch bhi ise kabhi nahi rokta
boom(0)

Forecast: Lagbhag kaunsa call number crash trigger karta hai?

Base case dhundho. Koi nahi hai — koi if ... return nahi. Yeh step kyun? Bina ruk jaane wali return ke recursion sirf limit hit karke hi khatam ho sakti hai.
Depth per call. Har call ek plate push karta hai aur kabhi pop nahi karta (inner call pehle finish hona chahiye, lekin woh kabhi nahi hota). $d$ = call number. Yeh step kyun? Yeh Cell C ki signature hai: upar ki figure mein red line — ek monotone climb, koi relief nahi.
Crash point. $k$ pre-existing frames ke saath, yeh call $1000 - k$ ke aas paas marta hai. Yeh step kyun? Woh formula box ki inequality hai, saturated ( $d = 1000 - k$ ).

Verify: clean start ke saath ( $k \approx$ kuch), crash call ≈ 996–999 ke paas, kabhi 1000 se zyada nahi. RecursionError guaranteed.

Dekho Recursion — base case and recursive case — Cell C exactly "base case bhool gaya" hai.

Cell D — base exist karta hai lekin kabhi approach nahi hota (woh chhupa hua)

Worked example Example 3 — base case jo ek decoy hai (Cell D)

def stuck(n):
    if n == 0:
        return 1          # ek real base case...
    return stuck(n + 1)   # ...lekin hum ussse DUR ja rahe hain
stuck(5)

Forecast: Ek if n == 0 hai. Kya woh humein bachata hai?

Travel ki direction check karo. Hum 5 se shuru karte hain aur stuck(6), stuck(7), ... call karte hain. Yeh step kyun? Base 0 par hai; har step $n$ badhata hai, isliye hum kabhi uspar land nahi karte — plate pile upar ki figure ki red runaway line follow karta hai, bilkul Cell C ki tarah.
Cell C se compare karo. Behaviour no-base-case jaisa hi hai: monotone climb to the limit. Yeh step kyun? Practice mein unreachable base case ka worth exactly zero hai.
Fix. stuck(n - 1) mein change karo aur base n <= 0. Yeh step kyun? Ab har call strictly 0 ki taraf approach karta hai (dekho Recursion — base case and recursive case).

Verify: stuck(5) RecursionError raise karta hai; fixed stuck(n-1) version 1 return karta hai aur peak depth $5 + 1 = 6$ reach karta hai.

Cell F — wrong-direction / negative input

Worked example Example 4 — ek sahi function jo ek bura number fed kiya gaya (Cell F)

def down(n):
    if n == 0:
        return 0
    return down(n - 1)
down(-4)

Forecast: Function positives ke liye theek hai. $n = - 4$ ke liye kya hota hai?

Sign follow karo. down(-4) → down(-5) → down(-6) → ... Yeh step kyun? Negative se 1 subtract karne par 0 se door jaata hai, uski taraf nahi — Cell C figure ki same red runaway climb.
Cell recognize karo. Negative input ke liye yeh sahi dikhne wala function Cell D jaisa behave karta hai — base ko overshoot karta hai aur bhaag jaata hai. Yeh step kyun? Base n == 0 sirf $n \geq 0$ se reachable hai.
Robust fix. if n <= 0: return 0 use karo. Yeh step kyun? <= base par ya neeche ki har value ko pakad leta hai, isliye negatives turant ruk jaate hain.

Verify: down(-4) RecursionError raise karta hai; n <= 0 ke saath woh peak depth 1 par 0 return karta hai (base pehli call par hi fire hota hai).

Cell G — branching recursion (depth ≠ call count)

Worked example Example 5 — Fibonacci: bahut saari calls, shallow stack (Cell G)

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)
fib(6)

Forecast: fib(6) dozens of calls karta hai. Kya ise stack overflow ka darr hai?

Total calls count karo. fib(6) total 25 calls trigger karta hai. Yeh step kyun? Log is number se darte hain — lekin total calls woh nahi hai jo limit check karti hai.
Sabse lamba path dhundho, sabse chauda nahi. Python fib(n-1) fully evaluate karta hai (neeche fib(1) tak pahunchte hue) fib(n-2) ko touch karne se pehle. Sabse deep single chain hai $n \to n - 1 \to \dots \to 1$ . Yeh step kyun? Depth frames hain jo ek pal mein stacked hain; do branches kabhi bhi ek saath fully open nahi hote.
Peak depth compute karo. 6 se base tak ka sabse lamba chain = frames for $n = 6, 5, 4, 3, 2, 1$ → $d =$ 6. Yeh step kyun? Two-way branching ke liye peak depth sabse lamba root-to-leaf path ki length hai, total node count nahi — ise seedha neeche ke tree mein red path se padho.

Verify: fib(6) = 8; total calls $= 25$ ; peak depth $d = 6$ , 1000 se aaram se neeche. Branching time ko explode karta hai, depth ko nahi.

Cell B + J — sahi logic, depth over the limit, exact-count twist

Worked example Example 6 — deep-but-legal sum, aur exam off-by-one (Cells B, J)

def depth_sum(n):
    if n == 0:
        return 0
    return n + depth_sum(n - 1)
depth_sum(2000)   # RecursionError — logic theek hai, depth bahut badi hai

Forecast: Maths perfect hai. depth_sum(2000) phir bhi crash kyun karta hai — aur default limit ke saath fresh REPL se kaam karne wala sabse bada n kya hai?

Peak depth. depth_sum(n) $d = n + 1$ reach karta hai (Cell A rule). $n = 2000$ ke liye woh 2001 hai. Yeh step kyun? $2001 > 1000$ , isliye plate pile dashed limit line se paar ho jaata hai mid-descent mein bhi tab jab har line sahi ho — yeh Cell B hai.
Sabse safe $n$ ke liye solve karo. Formula box se, $d \leq recursionlimit - k$ with $d = n + 1$ , toh $n + 1 \leq 1000 - k \Rightarrow n \leq 999 - k$ . Yeh step kyun? Limit saare frames count karti hai; $k$ pehle se call karne par present hain. Yeh Cell J twist hai.
$k = 2$ plug in karo (module + calling frame): $n \leq 999 - 2 = 997$ . Yeh step kyun? Yeh dikhata hai ki answer 999 nahi hai — pre-existing frames jagah churaate hain, parent ke "≈ 1000 − k" se match karta hai.

Verify: $n = 2000$ ke liye peak depth $2001 > 1000$ hai → RecursionError. Safe- $n$ bound $n \leq 999 - k$ deta hai $n \leq 997$ for $k = 2$ .

Cell A (iterative escape) — ek frame hamesha ke liye

Worked example Example 7 — iterative rewrite (Cell A, no growth)

def depth_sum_iter(n):
    total = 0
    while n > 0:
        total += n
        n -= 1
    return total
depth_sum_iter(2_000_000)

Forecast: Example 6 jaisa hi maths lekin loop ke saath. Do million ke liye stack kitna deep jaata hai?

Frames count karo. while loop depth_sum_iter ka single frame reuse karta hai. Yeh step kyun? Ek loop variables ko in place update karta hai — woh kabhi bhi ek call pause karke doosra start nahi karta, isliye plate pile puri time exactly ek plate ki unchai par hota hai.
Depth constant hai. n kitna bhi bada ho, $d$ 1 par rehta hai. Yeh step kyun? Yeh Iteration vs Recursion ka saara point hai: iteration stack growth ko ek loop counter ke saath trade karta hai.
Check karo ki woh abhi bhi sahi total return karta hai. depth_sum_iter(4) ko recursive depth_sum(4) ke barabar hona chahiye: $4 + 3 + 2 + 1 = 10$ . Yeh step kyun? Ek rewrite wahi value deni chahiye, sirf ek shallower depth ke saath — same answer, $d = 1$ instead of $d = n + 1$ .

Verify: depth_sum_iter(4) = 4+3+2+1 = 10 (depth_sum(4) se match karta hai); peak depth $d$ 1 par rehta hai 2,000,000 ke liye bhi. Koi RecursionError possible nahi.

Cell K — mutual (co-)recursion, ek shared stack

Worked example Example 8 —

is_even aur is_odd ek doosre se bounce karte hain (Cell K)

def is_even(n):
    if n == 0: return True
    return is_odd(n - 1)
def is_odd(n):
    if n == 0: return False
    return is_even(n - 1)
is_even(4)

Forecast: Do alag functions ek doosre ko call karte hain. Kya unhe har ek apna private stack limit milta hai?

Bounce trace karo. is_even(4) → is_odd(3) → is_even(2) → is_odd(1) → is_even(0) → True. Yeh step kyun? Har step $n$ ko 1 se drop karta hai, functions alternating karte hain — plate pile ko parwah nahi ki kaunse function ne plate rakhaa; yeh ek shared stack hai.
Combined depth count karo. Peak par paanch frames alive hain: is_even(4), is_odd(3), is_even(2), is_odd(1), is_even(0). Toh $d = n + 1 = 5$ . Yeh step kyun? Formula box ka $d$ ek stack par saare frames count karta hai, isliye do mutually-recursive functions ek hi 1000-frame budget share karte hain, do alag nahi.
Same failure modes apply karte hain. Kisi bhi function mein base case bhool jao aur tumhe Cell C milega; negative feed karo aur Cell F milega. Yeh step kyun? Mutual recursion ek naya khatra nahi hai — woh same plate pile hai jisme do labels alternate ho rahe hain.

Verify: is_even(4) True hai; is_odd(4) False hai; peak depth $d = 4 + 1 = 5 \leq 1000$ .

Cell H — deep-but-finite kaam ke liye limit badhana

Worked example Example 9 — deep-but-finite recursion, limit purposely raise ki (Cell H)

import sys
sys.setrecursionlimit(3000)     # deep-but-finite: 1500 + headroom
def depth_sum(n):
    if n == 0:
        return 0
    return n + depth_sum(n - 1)
depth_sum(1500)                 # ab legal hai: 1501 frames chahiye

Forecast: depth_sum(1500) ko peak depth 1501 chahiye — default 1000 se zyada. Kya limit badhana woh blind mistake hai jiske baare mein parent ne warn kiya, ya yeh sahi call hai?

Kya depth finite hai? Haan — $d = n + 1 = 1501$ , ek known, bounded number. Yeh step kyun? Cell H legitimate sirf tab hai jab depth finite ho aur tum uska maximum name kar sako.
Naya limit choose karo. Chahiye $limit > d + k = 1501 + k$ . Set karo $3000$ — roughly double — $k$ pre-existing frames ke liye generous headroom chhodke. Yeh step kyun? Formula box se, safety hai $d + k \leq recursionlimit$ ; known peak ko double karna comfortable slack hai.
Yeh blind mistake kyun nahi hai. Blind version infinite (Cell C/D) recursion ko "fix" karne ke liye limit raise karta hai aur segfault mein sail ho jaata hai. Yahan recursion $d = 1501$ par terminate karta hai. Yeh step kyun? Khatra unbounded depth hai, large-but-finite nahi.

Verify: required limit $> 1501 + k$ ; chosen $3000 \geq 1502$ → safe. Peak depth $d = 1500 + 1 = 1501$ , ek finite number jo raised limit accommodate karta hai.

Cell I — ek real-world word problem

Worked example Example 10 — nested-folder size walk (Cell I)

Story: Ek backup tool ek directory tree walk karta hai, file sizes total karne ke liye har sub-folder mein recurse karta hai. Ek user ki machine par folders 1500 deep nested hain. Tool mein ek sahi base case hai (bina sub-folders wala folder sirf apni file sizes return karta hai). Sabse neeche ke teen files par sizes 1, 2, aur 4 bytes hain. Kya default-limit tool crash karega, aur woh chhoti teen-file leaf par kya total hona chahiye?

def tree_size(folder):
    if folder.is_leaf():                       # base: koi sub-folders nahi
        return sum(folder.file_sizes)          # e.g. [1, 2, 4]
    return sum(tree_size(sub) for sub in folder.subfolders)

Forecast: "1500 folders deep" ko peak depth mein translate karo. Kya yeh 1000 se neeche fit hota hai?

Story ko depth mein translate karo. Har nesting level = ek recursive call = ek frame. 1500 levels → peak depth $d = 1500$ (plus leaf frame ≈ 1501). Yeh step kyun? Ek word problem real structure ko plate pile par map karke solve hota hai — folders deep hi depth hai.
Default limit se compare karo. $1501 > 1000$ , isliye default limit ke saath sahi tool crash karta hai RecursionError ke saath — yeh ek real Cell B situation hai jo real data se trigger hui. Yeh step kyun? Bug code mein nahi hai; input ki depth budget se zyada hai.
Leaf total karo. Bottom teen-file folder ke liye, sum([1, 2, 4]) = 7 bytes. Yeh step kyun? Sanity-check ki base case obvious haath-se-compute kiya hua answer deta hai, toh hum recursion ke leaves par trust karte hain.

Verify: peak depth $\approx 1501 > 1000$ → default limit par crash karta hai (fix: sys.setrecursionlimit(3000) jaisa Example 9 mein, kyunki 1500 finite hai). Leaf total sum([1,2,4]) = 7 bytes.

Cell A + Exceptions — pakdo aur recover karo

Worked example Example 11 — graceful

try/except, aur overflow par kya return karta hai (Cell A, defensive)

import sys
def safe_factorial(n):
    try:
        if n <= 1:
            return 1
        return n * safe_factorial(n - 1)
    except RecursionError:
        return None            # signal "compute karne ke liye bahut deep"
safe_factorial(5)              # normal path
safe_factorial(100_000)        # overflow path (limit se bahut paar)

Forecast: $n = 5$ ke liye hum limit ke kahin paas nahi hain — try/except yahan actually kya karta hai, aur ek huge $n$ ke liye kya wapas aata hai jo overflow karta hai?

Normal path. $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$ , base at n <= 1, peak depth $d = 5$ . Yeh step kyun? Chhota $n$ → Cell A, except kabhi fire nahi karta, isliye try yahan invisible hai.
Overflow path. $n = 100000$ ke liye plate pile ~1000 line se guzar jaata hai; inner call RecursionError raise karta hai. Woh error nearest try tak propagate hoti hai, jo ise pakad leta hai aur except branch run karta hai. Yeh step kyun? RecursionError ek normal exception hai, isliye yeh stack ko handler tak exactly kisi bhi doosri tarah unwind karta hai (dekho Exceptions and try-except in Python) — yeh precisely kyun Python ek hard segfault ki jagah soft, catchable limit use karta hai.
Kya return hota hai. Overflow par function None return karta hai, caller ko "too deep" detect karne aur react karne deta hai crash hone ki jagah. Yeh step kyun? Recovery ek dead program se better hai — soft limit hi is recovery ko possible banata hai.

Verify: safe_factorial(5) = 120; safe_factorial(1) = 1; $n = 5$ ke liye peak depth $d = 5 \leq 1000$ ; overflow path None return karta hai (ek RecursionError caught hai, propagated nahi).

Har cell ka 80/20

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