Recursion depth limit — stack overflow: Visual walkthrough

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

Yeh picture-first companion hai parent note ka. Agar yahan koi word jaldi-jaldi lagta hai, toh prerequisites hain Call stack and function frames, Recursion — base case and recursive case, aur Memory model — stack vs heap.

Step 1 — Ek single function call kya chhod jaati hai peeche

KYA. Jab tum ek function call karte ho, computer simply yeh bhool nahi sakta ki woh kya kar raha tha. Woh ek chhota note-card likhta hai jise stack frame kehte hain. Us card mein teen cheezein hoti hain: call ke arguments (inputs), uske local variables (scratch values), aur ek return address (caller mein exactly woh jagah jahan wapas jump karna hai jab yeh call done ho jaaye).

YEH TEEN HI KYUN, kuch aur nahi? Kyunki yahi exactly woh cheezein hain jo paused caller ko baad mein resume karne ke liye chahiye hoti hain. Arguments + locals = call ki private memory; return address = "main kahan tha?". Inme se koi ek bhi drop karo toh tum correctly wapas nahi aa sakte.

PICTURE. Neeche woh single yellow card dekho. Teen labelled rows hi iske akeele contents hain. Card ek unit hai — ab se, ek call = ek card.

Figure — Recursion depth limit — stack overflow

Step 2 — Cards ek LIFO pile par jaate hain: the call stack

KYA. Yeh cards idhar-udhar scattered nahi hote. Inhe ek single pile mein stack kiya jaata hai jise call stack kehte hain. Nayi calls ek card upar rakhti hain (ise push kehte hain); ek finished call top ka card uthaati hai (ek pop).

STACK KYUN, koi queue kyun nahi? Kyunki calls ulte order mein finish hoti hain jis order mein shuru hui theen: sabse recent call woh hai jo abhi chal rahi hai, toh use pehle finish karna hoga. "Last in, first out" — LIFO — woh ek aur akela ordering hai jo isse match karta hai. Stack word literal hai: dinner plates sochho, tum sirf upar se touch karte ho.

PICTURE. Neeche ki pile upar ki taraf badhti hai. Daayein taraf ka green arrow ek push dikhata hai (upar naya card); red arrow ek pop dikhata hai (top card remove ho raha hai). Sabse upar ka card hamesha woh hota hai jo abhi chal raha hai.

Step 3 — Ek acchi recursion: pile upar jaati hai, phir drain hoti hai

KYA. Ek recursion dekho jiska base case hai aur woh actually use tak pahunchti hai. depth_sum lo:

def depth_sum(n):
    if n == 0:            # base case — finish line
        return 0
    return n + depth_sum(n - 1)   # step 0 ki taraf badhta hai

depth_sum(3) call karne par n=3, 2, 1, 0 ke liye cards push hote hain. n=0 par base case return karta hai — koi naya card nahi — toh cards wapas neeche pop hone lagte hain.

YEH DRAIN KYUN HOTI HAI? Kyunki har recursive call n - 1 use karti hai, strictly chhota. Argument $3 \to 2 \to 1 \to 0$ chalता hai aur base case hit karta hai. Ek baar ek card return kar deta hai, pile sirf shrink ho sakti hai. Yahi hai ek reachable base case ka poora matlab.

PICTURE. Left half pile ko height 4 tak rise karte dikhata hai; middle n=0 ko base case hit karte mark karta hai (green); right half ise wapas zero tak drain hote dikhata hai. Shape notice karo: ek pahaad jo wapas neeche aata hai.

Step 4 — Ek tooti hui recursion: pile sirf upar jaati hai

KYA. Ab finish line bilkul hata do:

def boom(n):
    return boom(n + 1)    # koi base case nahi, aur n kisi base se door jaata hai
boom(0)

Har call return karne se pehle ek aur call karti hai, toh koi card kabhi pop nahi hota. Argument $0 \to 1 \to 2 \to \dots$ jaata hai — galat direction agar hum kisi chhote base tak pahunchne ki umeed kar rahe the.

YEH KABHI DRAIN KYUN NAHI HOTI? Ek card tab pop hota hai jab uski call ek value return karti hai. Lekin boom ki return line pehle inner boom(...) ko finish karna chahti hai — jo kabhi finish bhi nahi hoti. Toh n=0 ke liye "return" hamesha ke liye postpone ho jaata hai. Pile sab rise hai, koi fall nahi.

PICTURE. Step 3 se compare karo. Koi green base card nahi, koi peak nahi, koi descent nahi — sirf ek hamesha uunchaa hota yellow tower hai jo frame ke top se bahar nikalta ja raha hai.

Step 5 — Stack memory ek chhoti, fixed shelf hai

KYA. Call stack unlimited space mein nahi rehta. Operating system har program ko stack memory ka ek fixed, chhota slab deta hai — aksar sirf 1–8 MB. Ise heap se compare karo (dekho Memory model — stack vs heap), jo gigabytes ka ho sakta hai.

YEH MATTER KYUN KARTA HAI? Har card free nahi hai — woh us slab ka ek chunk occupy karta hai. Cards ek hard ceiling wali shelf ke andar upar pile hote hain. Ek infinite tower (Step 4) eventually us ceiling se zaroor takraayega.

PICTURE. Tall thin box stack shelf hai. Uske paas mein heap wide draw kiya gaya hai size gap dikhane ke liye. Cards shelf ko bottom se bharte hain; top ke paas dashed red line physical ceiling hai.

Step 6 — Python real ceiling se pehle ek soft line kheenchta hai

KYA. CPython pile ki height count karta hai aur apni khud ki limit enforce karta hai, recursion limit (default 1000 frames), jo real memory ceiling ke neeche hoti hai. Ise cross karo aur Python shelf ko overflow hone dene ki jagah ek catchable RecursionError raise karta hai.

SOFT LINE KYUN, CRASH KA INTEZAAR KYUN NAHI? Do wajahaat. (1) Ek real overflow ek segfault hai — koi message nahi, koi traceback nahi, recover karne ka koi tarika nahi. (2) Ek RecursionError ek ordinary exception hai, toh try/except ise catch kar sakta hai (dekho Exceptions and try-except in Python). Python thodi si allowed depth ke liye ek graceful, debuggable failure ka trade karta hai.

PICTURE. Step 5 wahi shelf hai, lekin ab "depth 1000" par ek yellow dashed line red physical ceiling ke neeche hai. Tower pehle yellow line se takraata hai — wahan RecursionError fire karta hai, safely disaster se neeche.

Step 7 — Limit sirf tumhare cards nahi, sabhi cards count karti hai

KYA. Limit ek total-frame count hai. Jab tumhari recursion shuru hoti hai, pile khaali nahi hoti — module, aur REPL mein interactive machinery, already us par baithe hain. Maan lo $k$ cards already wahan hain. Toh tumhari recursion sirf roughly $1000 - k$ aur add kar sakti hai.

CARE KYUN KAREIN? Isliye depth_sum(998) crash kar sakta hai bhaale hi $998 < 1000$ ho: pre-existing $k$ cards tumhara budget kha jaate hain. Limit per-stack hai, per-function nahi.

PICTURE. Pile $k$ pre-existing cards ke ek chhote grey base se shuru hoti hai. Tumhari recursion ke yellow cards upar stack hote hain, aur crash tab aata hai jab combined height 1000 reach karti hai — toh tumhara usable slice woh chhota yellow segment hai.

Step 8 — Do honest fixes (nahi ki "limit badha do")

KYA. Tum $L$ raise karne ke liye sys.setrecursionlimit(N) call kar sakte ho. Lekin ise bahut zyada raise karne par yellow line real ceiling ke upar chali jaati hai — ab soft guard bekar hai aur tum real segfault mein gir jaate ho. Robust fixes hain:

Base case reach karo. Har call ko strictly finish line ki taraf approach karo (Step 3 ka shape).
Iteration use karo. Ek loop hamesha ke liye ek frame reuse karta hai — pile kabhi nahi badhti. Dekho Iteration vs Recursion.

ITERATION POORI TARAH KYUN BACHA LETA HAI? Ek while loop har step mein ek naya card push nahi karta; woh apne single frame ke andar variables update karta hai. Depth 1 rehti hai chahe kitni bhi iterations hon. (Python tumhare liye deep recursion auto-convert nahi karta — dekho Tail recursion and why Python lacks tail-call optimization.)

PICTURE. Left: recursion, ek badhta tower. Right: iterative rewrite, ek flat card jiske andar ka counter change hota hai jabki pile height 1 par pinned rehti hai.

Worked example

depth_sum ka iterative twin

def depth_sum_iter(n):
    total = 0
    while n > 0:
        total += n
        n -= 1
    return total
depth_sum_iter(2_000_000)   # depth 1 rehti hai, kabhi overflow nahi hoti

Ek frame, ek total, koi pile nahi. Woh 2-million-step loop jo recursion ko tabah kar deta, yeh fine chalti hai.

Ek-picture summary

Sab kuch ek single storyboard mein compress hota hai: ek acchi recursion rise hoti hai phir drain hoti hai (mountain), ek buri forever rise hoti hai soft line mein (crash), aur iteration flat rehti hai.

Recall Feynman retelling — poora walk plain words mein

Jab bhi ek function khud ko call karta hai, computer ek chhota note-card likhta hai ("main kya kar raha tha, aur main kahan wapas jaata hoon?") aur ise ek pile par daal deta hai. Pile plates ka ek stack hai: sabse nayi upar, aur tum sirf upar se le sakte ho. Ek acchi recursion — jiske paas ek real finish line hai jis ki taraf woh actually chalti hai — pile ko upar badhati hai, finish line hit karti hai, aur phir plate ke baad plate wapas uthati hai: ek pahaad jo neeche aata hai. Ek tooti hui recursion kabhi finish line tak nahi pahunchti, toh woh sirf plates stack karti rehti hai aur kabhi ek nahi hatati. Lekin plates rakhne wali shelf tiny hai (kuch megabytes), jabki "bada table" (heap) enormous hai — toh endless pile zaroor ceiling se takraayegi. Agar woh actually shelf ki ceiling se takraati, toh poora program silently aur horribly crash ho jaata (segfault). Toh Python takriban 1000 plates par ek chalk line kheenchta hai, real ceiling ke neeche, aur politely "RecursionError!" chillata hai jab tum ise cross karte ho — ek crash jo tum catch aur fix kar sakte ho. Aur kyunki pile par tumhare function ke shuru hone se pehle hi kuch plates hoti hain, tumhari apni recursion ko 1000 se thoda kam milta hai. Asli ilaaj chalk line raise karna kabhi nahi hota — woh hai recursion ko ek finish line dena jo woh reach kare, ya ek plain loop use karna jo ek plate hamesha ke liye reuse kare.

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