Recursion depth limit — stack overflow — Hinglish notes

1.2.39 · Coding › Introduction to Programming (Python)

HOW — step by step kaise kaam karta hai

Ek infinite recursion consider karein (classic bug):

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

Worked example Stack growth ko trace karna

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

Yeh step kyun? Har call pehle hoti hai jab previous wali return nahi hoti, toh koi frame kabhi pop nahi hoti. Depth har call par 1 badhti hai jab tak limit tak nahi pahunch jaati.

Figure — Recursion depth limit — stack overflow

Limit ko inspect aur change karna

Formula Limit ko read aur set karna

$depth at crash \leq recursionlimit$

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

Practice mein exactly 1000 kyun nahi hoti, iska derivation: limit saare frames count karti hai, including woh jo aapke start karne par already stack par hote hain (module, REPL, etc.). Toh agar $k$ frames already exist karte hain, aapki recursion sirf lagbhag $1000 - k$ deep ja sakti hai. Bound ek total-frame count hai, per-function count nahi.

Worked examples

Worked example Example 1 — Deep lekin 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

Yeh step kyun? depth_sum(2000) ko ek saath 2001 stacked frames chahiye — 1000 se kaafi zyada. Logic sahi hai, lekin depth limit se zyada hai. Fix: ya toh sys.setrecursionlimit(3000) ya iteratively rewrite karo.

Worked example Example 2 — Iterative rewrite (koi stack growth nahi)

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

Yeh step kyun? Ek loop ek frame reuse karta hai; variable total ek call ke heap-friendly stack par rehta hai. Koi frames pile up nahi hote → n chahye kitna bhi ho, koi overflow nahi.

Worked example Example 3 — Error ko catch karna

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"

Yeh step kyun? RecursionError ek normal exception hai, toh try/except kaam karta hai. Yahi kyun hai ki Python soft limit use karta hai segfault ke bajaay — aap recover kar sakte ho.

80/20 takeaway

Flashcards

Active function calls kaun sa data structure store karta hai?

Call stack (LIFO), jo har active call ke liye ek stack frame rakhti hai.

Stack frame kya cheezein rakhta hai?

Call ki local variables, arguments, aur return address (caller mein kahaan resume karna hai).

Recursion depth define karo.

Recursion ke dauran ek saath active (paused) stack frames ki sankhya.

CPython mein default recursion limit kya hai?

Lagbhag 1000 total frames.

Python bahut deep recursion par kaun sa error raise karta hai?

RecursionError: maximum recursion depth exceeded.

Python crash karne ki jagah soft limit kyun use karta hai?

Taaki OS ke hard, uncatchable stack overflow (segfault) se pehle ek catchable RecursionError raise ho sake.

Limit ko kaise read aur change karte hain?

sys.getrecursionlimit() aur sys.setrecursionlimit(N).

setrecursionlimit badhana dangerous kyun hai?

Bahut zyada value recursion ko real stack memory exhaust karne de sakti hai, jisse uncatchable segfault ho sakta hai.

Limit hit karne ke do robust fixes?

Ensure karo ki ek correct base case ho jo actually approach ki jaati hai, ya algorithm ko iteratively rewrite karo.

Limit exactly 1000 of YOUR calls kyun allow nahi karti?

Yeh saare frames count karti hai, including pre-existing ones, toh available depth ≈ 1000 − (already-stacked frames).

Recall Feynman: ek 12-saal ke bache ko explain karo

Socho tum dinner plates stack kar rahe ho. Har baar jab ek function khud ko call karta hai, tum ek aur plate pile par rakh dete ho — woh plate yaad rakhti hai function kya kar raha tha. Jab sabse deep wala function khatam hota hai, tum ek plate neeche le aate ho. Lekin agar ek function khud ko call karta rehta hai aur kabhi khatam nahi hota, tum plates stack karte rehte ho hamesha ke liye. Aakhirkar pile bahut zyada unchi ho jaati hai aur floor par crash ho jaati. Python smart hai: lagbhag 1000 plates par woh chillata hai "RUKO! RecursionError!" ki puri cheez gir jaaye. Ise sach mein fix karne ke liye, function ko ek clear finish line (base case) do jo woh actually reach kare — ya ek simple loop use karo jo sirf ek plate baar baar use karta hai.

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

Recursion depth limit — stack overflow

KYA ho raha hai

KYUN ek limit hoti hai