Recursion — call stack visualization, base case, recursive case: Question bank

1.2.37 · D5 · Coding › Introduction to Programming (Python) › Recursion — call stack visualization, base case, recursive c

Intuition Is page ko kaise use karein

Neeche har line ek trap hai jo recursion ka topic set karna pasand karta hai. Left side padho, apna jawab zyoor se bold bolke commit karo, PHIR reveal karo. Agar tumhari reasoning right side se match karti hai, tab tum sach mein samjhe ho — lucky guess count nahi hoti. Ye target karte hain understanding ko, arithmetic ko nahi (heavy tracing ke liye parent topic note dekho).

Neeche use hua naya vocabulary, sab parent note mein build hua hai:

frame = memory ka woh chhota box jo ek call ke apne variables hold karta hai (dekho The Call Stack and Stack Frames).
winding = neeche jaana, frames push karna; unwinding = wapis upar aana, frames pop karna.
base case = woh input jo bina aage call kiye answer ho jaaye; recursive case = woh part jo khud ko chhote input par call kare.

True or false — justify

Ek recursive function mein hamesha exactly ek base case hona chahiye.

False. Usse kam se kam ek chahiye, lekin kai ho sakte hain — jaise Fibonacci dono n == 0 aur n == 1 ke liye directly return karta hai. Rule hai "har path down ko koi na koi base case hit karna chahiye", na ki "exactly ek hai".

Agar input har call par chhota hota jaaye, toh recursion guaranteed rukegi.

False. Chhota input akela kaafi nahi — ek value ko actually base case ke zariye catch aur return karna zaroori hai. Bina if n == 0: return ... ke, shrinking

0

se seedha fact(-1), fact(-2), … tak forever nikal jaayegi.

Har recursive function ko ek loop ke roop mein rewrite kiya ja sakta hai.

True. Recursion aur iteration equally powerful hain; kisi bhi recursion ko ek explicit stack aur ek while loop se simulate kiya ja sakta hai (dekho Iteration — for and while loops). Recursion often sirf maths ke zyada kareeb hoti hai, zyada capable nahi.

fact(3) ke saare stack frames variable n ka ek hi copy share karte hain.

False. Har call ko apna independent frame milta hai, toh n = 3, n = 2, n = 1, n = 0 sab sabse gehre moment par saath mein exist karte hain. Same naam, alag boxes.

fact(3) ke dauran, call fact(3) apni value fact(0) se pehle return karti hai.

False. Stack LIFO hai: sabse aakhir mein push hua frame (fact(0), base case) sabse pehle finish hota hai, phir baaki bahar ki taraf unwind hote hain. fact(3) sabse aakhir mein return karta hai.

Recursion hamesha equivalent loop se slower ya zyada memory-hungry hoti hai.

Memory ke mamle mein usually true (har frame stack space leta hai, depth 1000 ke paas cap hota hai), lekin "hamesha" bahut strong hai — memoization ke saath ek recursive solution ek naive loop se match kar sakta hai ya beat bhi. Clarity, speed nahi, recursion ki main win hai.

Ek function jo ek alag function ko call kare jo phir pehle wale ko wapis call kare, woh recursion nahi hai.

False. Yeh mutual (indirect) recursion hai — is_even(n) jo is_odd(n-1) call karta hai jo is_even(n-2) call karta hai. Recursion ka matlab hai "eventually khud ko call karna", directly ya chain ke through.

return keyword recursive case mein optional hai jab tak tum answer print karo.

Ek value compute karne ke liye False. Bina return ke, sub-call ka result discard ho jaata hai aur function None yield karta hai. Printing screen par ek number dikhata hai lekin caller ko combine karne ke liye kuch wapis nahi deta.

Spot the error

def f(n): return n * f(n-1) — kya missing hai aur kya hoga?

Koi base case nahi, toh yeh kabhi nahi rukta. Python frames push karta hai jab tak depth limit nahi hit hoti → RecursionError: maximum recursion depth exceeded. Add karo if n == 0: return 1.

def f(n): if n==0: return 1; return n * f(n) — yeh phir bhi crash kyun karta hai?

Recursive call f(n) use karta hai, f(n-1) nahi, toh input kabhi chhota nahi hota. Yeh ek jaisi problem hamesha se poochh raha hai aur base case hone ke bawajood kabhi nahi pahunchta.

def summ(L): if not L: return 0; L[0] + summ(L[1:]) — yeh kya return karta hai aur kyun?

Yeh None return karta hai. Aakhri line sum compute karti hai lekin koi return nahi hai, toh value throw ho jaati hai. Fix: return L[0] + summ(L[1:]).

def cd(n): print(n); if n==0: return; cd(n-1) ko cd(2) ke liye — kya yeh sahi hai?

Yeh placement ki luck se kaam karta hai. print check se pehle hai, toh yeh 2, 1, 0 print karta hai phir ruk jaata hai. Pehle base case test karna zyada clean hai; yahan ek negative call sirf isliye avoid hoti hai kyunki n==0 cd(-1) se pehle return kar deta hai.

def fib(n): if n<=1: return n; return fib(n-1) + fib(n-1) — bug dhundho.

Dono branches n-1 par recurse karte hain; doosra fib(n-2) hona chahiye. Jaise likha hai yeh galat sequence compute karta hai (aur phir bhi terminate hota hai, toh koi crash warn karne ke liye nahi — ek silent logic bug). Dekho Fibonacci and overlapping subproblems.

def f(n): if n==0: return 1 else: return n*f(n-1) ko f(2.5) ke roop mein call kiya — problem?

Input har baar 1 se ghatta hai (2.5 → 1.5 → 0.5 → −0.5 → …) lekin kabhi exactly 0 ke barabar nahi hota, toh base case hamesha skip ho jaata hai → RecursionError. Base cases starting input se reachable hone chahiye.

def down(n): if n==0: return; down(n-1); print(n) ko down(3) ke liye — kya print hoga?

1 2 3, 3 2 1 nahi. print recursive call ke baad hai, toh yeh unwinding ke dauran run hota hai (wapis upar aate waqt), visible order ko reverse kar deta hai.

Why questions

Base case ko code mein recursive call se pehle kyun aana chahiye?

Taaki stopping condition pehle check ho, har entry par. Agar recursive call check se pehle run hoti, toh tum kabhi bhi "kya mujhe rukna chahiye?" poochhe bina ek level bahut neeche chale jaate (ya infinitely).

Sabse gehri recursive call sabse pehle kyun finish hoti hai?

Kyunki call stack LIFO hai — sabse aakhir mein push hua frame sabse pehle pop hota hai. Har caller apne callee ka intezaar karte hue paused hota hai, toh neeche wala return kare tab tak upar ka koi bhi resume nahi ho sakta.

Do frames mein dono n naam ka variable ho sakta hai bina clash kiye?

Har function call ek fresh frame apne local namespace ke saath create karta hai. Naam n us frame ke box ke andar ek label hai, toh fact(3) ka n aur fact(2) ka n bilkul alag storage hain.

print ko recursive call se pehle se baad mein le jaane par output order kyun reverse ho jaata hai?

Call se pehle ek print winding ke dauran fire hoti hai (top-down); call ke baad yeh unwinding ke dauran fire hoti hai (bottom-up). Dono phases values ko opposite orders mein visit karte hain.

Naive recursive Fibonacci slow kyun hai jabki har call input chhota karti hai?

Kyunki yeh same subproblems kai baar re-solve karta hai — fib(3) poore tree mein baar baar recompute hota hai. Kaam exponentially blast hota hai; Memoization and Dynamic Programming ise har answer ek baar cache karke fix karta hai.

Recursion folder tree walk karne ya nested data parse karne ke liye natural kyun hai?

Woh structures self-similar hain: ek folder mein folders hain, har ek same tarike se handle hota hai. Recursion us shape ko directly mirror karta hai — dekho Tree and Graph Traversal.

Python recursion depth ko 1000 ke paas cap kyun karta hai unlimited calls allow karne ki jagah?

Har pending frame real stack memory occupy karta hai; unbounded depth use exhaust kar deta aur interpreter ko unpredictably crash kar deta. Cap ek silent memory blow-up ko ek catchable RecursionError mein turn kar deta hai. Dekho Big-O and Recursion Depth.

Edge cases

fact(0) kya return karta hai, aur yeh poora point kyun hai?

Yeh bina kisi recursive call ke immediately 1 return karta hai. Woh direct answer base case hai — woh zameen jis par calls ki poori staircase khadi hai; isse hatao aur sab kuch collapse ho jaata hai.

Jab tum summ([]) (empty list) call karo toh kya hota hai?

Base case if not L: return 0 turant fire hota hai. Ek empty problem ka ek known trivial answer hota hai, toh koi recursion ki zaroorat nahi — yeh bilkul kyun base cases exist hain.

Agar ek recursive call sabse pehli cheez hai jo run hoti hai (kisi bhi base check se pehle), toh kya toot jaata hai?

Function kabhi test kiye bina ki rukna chahiye ya nahi recurse karta hai, toh yeh indefinitely descend karta hai aur stack overflow ho jaata hai. Stop condition ko next call se pehle reachable hona chahiye.

Ek single-element list summ([7]) ke liye, kya recursion hogi bilkul?

Haan — [7] empty nahi hai, toh yeh 7 + summ([]) compute karta hai. Empty-list base case agli call par reach hoti hai, is par nahi. One-element inputs phir bhi ek recursive case hain, base case nahi.

Kya ek base case mein khud ek recursive call ho sakti hai?

Nahi — by definition base case recursion kiye bina return karta hai. Agar yeh recurse karta toh kuch bhi nahi rokta, aur descent ka koi guaranteed floor nahi hota.