Exercises — Recursion depth limit — stack overflow

• A — base case n==0 hai AUR har call uski taraf move karti hai (n-1). Non-negative n ke liye depth limit ke andar safe hai. (Note: negative n 0 ko overshoot kar dega aur kabhi nahi rukega — domain assumption matter karta hai.)
• B — bilkul base case nahi; n hamesha badhta hai. Hamesha overflow karta hai.
• C — base case hai, lekin C(n) C(n) ko call karta hai — yeh kabhi base ki taraf move nahi karta. Kisi bhi n>0 ke liye yeh hamesha overflow karta hai.

Answer: B aur C hamesha overflow karte hain. A nahi karta (non-negative n ke liye depth ≤ limit).

boom(0) frame 1 hai, boom(1) frame 2 hai, ..., boom(k) frame $k+1$ hai. $1000$ ka limit frames $1$ se $1000$ tak exist hone deta hai. Frame $1000$ hai boom(999) — woh call allowed hai. Agla call, boom(1000), frame $1001$ hoga, jo $1000$ se zyada hai, isliye boom(1000) woh call hai jo RecursionError raise karta hai. Key off-by-one: sabse deep call jo succeed hoti hai boom(999) hai (frame $1000$); pehli call jo fail hoti hai boom(1000) hai (frame $1001$).

Push order (har ek agla ka wait karta hai): depth_sum(4), depth_sum(3), depth_sum(2), depth_sum(1), depth_sum(0). Yeh $n+1=4+1=5$ frames simultaneously stacked hain. Tab hi jab depth_sum(0) 0 return karta hai frames popping shuru hoti hain (LIFO — last pushed, first popped).

Aapki recursion ke liye available depth $=1000-12=988$ frames. depth_sum(n) ko $n+1$ frames chahiye. Require $n+1\le 988\Rightarrow n\le 987$. Sabse badi safe value: $\mathbf{n}=987$.

Recursion ko chahiye frames: $2000+1=2001$. Sabse deep point par stack par total frames: $2001+30=2031$. Isliye aapko limit kam se kam $2031$ chahiye. sys.setrecursionlimit(2031) minimum hai; practice mein aap isse pad karte (jaise 3000) safety ke liye.

Nahi. Depth ek sabse lambi single chain of paused calls hai, calls ki total number nahi. Figure dekho: tree wide hai (bahut calls) lekin deepest path sirf n-1 branch se neeche jaata hai: fib(10) → fib(9) → fib(8) → ... → fib(1). Woh path $n=10,9,8,\dots ,1$ ke liye frames push karta hai, isliye frames $10,9,\dots ,1$ ke liye hain = maximum $10$ frames ek saath stacked. Total calls bahut zyada hai (fib(10) ke liye $177$ calls), lekin sab ek saath live nahi hote — do branches ek ke baad ek run hoti hain, isliye inke beech frames pop ho jaate hain.

Max depth hamesha-n-1 path follow karta hai: fib(n) → fib(n-1) → ... → fib(1), depth $=n$ deta hai $n\ge 1$ ke liye (aur depth $1$ $n=0$ ke liye). Total call count roughly ${\varphi }^n$ jaisa badhta hai, jahan $\varphi \approx 1.618$ golden ratio hai — ek fixed constant thoda $1$ se bada; isse $n$ power tak raise karne se count exponentially balloon karta hai jab $n$ badhta hai. Yeh ek time/repetition cost hai, sequentially pay ki jaati hai. Depth ek space cost hai, aur sirf currently paused frames count hote hain. Kyunki left subtree puri tarah finish ho jaati hai (apne frames pop karke) right subtree shuru hone se pehle, woh kabhi coexist nahi karte. Isliye depth = $n$ (linearly badhta hai), jabki call count $\approx {\varphi }^n$ (exponentially badhta hai).

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

Loop poore time ek frame reuse karta hai, isliye depth n ki parwah kiye bina $1$ rehti hai. $depth\_sum\_iter(100)=100+99+\cdots +1=\frac{100\cdot 101}{2}=5050$.

def depth_sum(n):
    if n == 0: return 0
    return n + depth_sum(n - 1)
 
def safe_depth_sum(n):
    try:
        return depth_sum(n)
    except RecursionError:
        return None

RecursionError ek ordinary exception hai (dekho Exceptions and try-except in Python), isliye try/except ise catch karta hai — yeh exactly kyun hai Python ek soft, catchable limit use karta hai segfault ki jagah. $safe\_depth\_sum(3)=3+2+1+0=6$.

(a) Sabse deep point par alive total frames $=D+k=8000+45=8045$. Minimum limit $=8045$. (b) Stack bytes used $=8045\times 600=4827000$ bytes ($\approx 4.60$ MiB). (c) Available $=8\times 1024\times 1024=8388608$ bytes. Kyunki $4827000<8388608$, haan, fit hoga — $8388608-4827000=3561608$ bytes bachte hain ($\approx 3.40$ MiB). Yeh disciplined tarika hai limit raise karne ka: pehle byte budget compute karo (dekho Memory model — stack vs heap), sirf "million tak crank mat karo."

Yeh tail recursion nahi hai: depth_sum(n-1) return hone ke baad, abhi bhi kaam karna hai — addition n + (...). Recursive call last cheez nahi hai jo hoti hai, isliye uska frame alive rehna chahiye result receive karne aur n add karne ke liye. (Dekho Tail recursion and why Python lacks tail-call optimization.) Even ek true tail-recursive version (accumulator-style, return helper(n-1, acc+n)) Python mein phir bhi overflow karega, kyunki CPython deliberately har frame rakhta hai (clean tracebacks ke liye) — iske paas koi tail-call optimization nahi hai. Isliye Python mein fix dono cases mein same hai: loop mein convert karo, constant depth $1$ deta hai. depth_sum_iter(100) = 5050 L4.1 se confirm karta hai ki loop recursion se match karta hai.

• No Base: missing YA unreachable base case (including ek step jo base se door move karta hai, jaise depth_sum ko negative input) matlab koi recursive call kabhi return nahi hoti.
• Frames Race: kyunki koi call return nahi hoti, koi bhi stack frame kabhi pop nahi hota, isliye recursion depth har call ke saath $1$ se badhti hai.
• Stack's out of Space: depth recursion limit ($\approx 1000$ total frames) cross kar leti hai, aur CPython ek catchable RecursionError raise karta hai pehle ki real, fixed-size stack memory khatam ho aur OS segfault kare.