Recursion — call stack visualization, base case, recursive case: Worked examples

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

The scenario matrix

Har recursive problem inhi cells mein se kisi ek mein hoti hai. Last column us example ka naam deta hai jo use cover karta hai.

#	Cell (scenario class)	Isme tricky kya hai	Covered by
A	Normal shrink-by-one	ordinary recursive case, ek branch	Example 1 (factorial)
B	Base case POORA input hi hai	input already tiny, koi recursion nahi chalti	Example 2 (`fact(0)`, `summ([])`)
C	Degenerate / invalid input	negative ya empty — kya yeh rukta hai?	Example 3 (`fact(-1)`)
D	Ek saath do base cases	do stops chahiye, ek nahi	Example 4 (Fibonacci)
E	Branching (tree-shaped) recursion	har call kai calls spawn karta hai	Example 4 (Fibonacci)
F	Shrink-by-halving (depth limit karta hai)	problem jaldi drop hoti hai, depth chhoti rehti hai	Example 5 (power via halving)
G	Order matters: call se pehle vs baad mein kaam	winding vs unwinding (phir bhi linear)	Example 6 (print order)
H	Real-world word problem	story → base + recursive case mein translate karo	Example 7 (Russian dolls)
I	Exam-style twist	subtle bug jo aapko spot karna hai	Example 8 (missing return)

Example 1 — Cell A: ordinary shrink-by-one

Worked example

fact(4) compute karo aur count karo kitne frames stack hote hain

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

Forecast: Final number guess karo, aur guess karo ki kitne frames sabse gehri jagah exist karte hain. Padhne se pehle likh lo.

Step 1 — Wind down karo, har baar ek frame push karte hue. fact(4) → 4 * fact(3) → 3 * fact(2) → 2 * fact(1) → 1 * fact(0). Yeh step kyun? Har call $n!$ ko $n \cdot (n - 1)!$ se replace karta hai — yeh self-similar rule hai. Har pause ek frame hai. Neeche figure mein tower ko badhte dekho (left to right, purple frames).

Step 2 — Neeche frames count karo. Alive frames: fact(4), fact(3), fact(2), fact(1), fact(0) = 5 frames. Yeh step kyun? Abhi tak kuch bhi return nahi hua — har paused call abhi bhi memory occupy kar rahi hai. Isliye deep recursion memory cost karta hai (dekho Big-O and Recursion Depth).

Step 3 — Base case hit karo, phir unwind karo. fact(0)=1, phir $1 \cdot 1 = 1$ , $2 \cdot 1 = 2$ , $3 \cdot 2 = 6$ , $4 \cdot 6 = 24$ . Yeh step kyun? Stack LIFO hota hai — Last-In-First-Out, matlab jo frame sabse last push hua woh pehle finish hoga aur remove hoga. Toh last-pushed frame (fact(0)) pehle finish hota hai, aur multiplications wापस aate waqt outside-in hoti hain. (Dekho The Call Stack and Stack Frames.)

Verify: $4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24$ . ✅ Frame count = $n + 1 = 5$ . ✅

Figure — Recursion — call stack visualization, base case, recursive case

Example 2 — Cell B: base case POORA input hi hai

Worked example

fact(0) aur summ([]) evaluate karo Pehle, yeh summ helper hai jo hum is poore page mein use karenge — yeh list ko first element nikalke aur baaki par recurse karke add karta hai:

def summ(L):
    if not L:                  # base case: empty list
        return 0
    return L[0] + summ(L[1:])  # recursive case: first + sum of the rest

Forecast: Yahan function khud ko kitni baar call karta hai? Ek number guess karo.

Step 1 — Pehle base condition check karo. fact(0) ke liye: if n == 0 turant True hai → 1 return karo. Yeh step kyun? Base case kisi bhi recursive call se pehle check hota hai. Agar yeh fire kare, toh bilkul bhi recursion nahi hoti — zero self-calls.

Step 2 — Empty list ke liye bhi same. summ([]): if not L True hai → 0 return karo. Yeh step kyun? Ek empty list sabse chhoti list hai; uska sum directly $0$ define hota hai.

Verify: exactly 1 frame kabhi exist karta hai (outer call), 0 recursive calls. fact(0)=1, summ([])=0. ✅ Yeh "already at the ground" case hai — koi seerhiyaan utrne ko nahi hain.

Example 3 — Cell C: degenerate / invalid input

Worked example

fact(-1) ke saath kya hota hai? Aur hum ise safe kaise banate hain? Forecast: Kya yeh ek number return karega, None return karega, ya crash karega? Guess karo.

Step 1 — Descent trace karo. n = -1: if n == 0 False hai → return -1 * fact(-2). Phir fact(-2), fact(-3), … Yeh step kyun? $n$ shrink ho raha hai, lekin yeh $0$ ko skip karke guzar jaata hai — yeh kabhi $0$ ke equal nahi hota, toh base case kabhi fire nahi karta.

Step 2 — Frames bina limit ke pile up hote rehte hain. Python frames stack karta rahta hai jab tak apni depth limit (~1000) na pahunch jaaye → RecursionError: maximum recursion depth exceeded. Yeh step kyun? Yeh parent ki warning prove karta hai: "smaller" hona bekar hai jab tak koi value caught na ho. Stop condition, shrinking nahi, recursion ko khatam karta hai.

Step 3 — Robust base test se fix karo.

def fact(n):
    if n <= 0:        # 0 AUR negatives dono ko pakadta hai
        return 1
    return n * fact(n-1)

Yeh step kyun? <= use karna har us input ko pakadta hai jo $0$ ko overshoot kare, toh fact(-1) ab crash hone ki jagah safely 1 return karta hai.

Verify: fix ke saath, fact(-1) == 1 aur fact(-5) == 1 (dono turant base hit karte hain). ✅

Example 4 — Cells D & E: do base cases + branching

Worked example

fib(5) compute karo jahan Fibonacci hai $F_{0} = 0, F_{1} = 1, F_{n} = F_{n - 1} + F_{n - 2}$

def fib(n):
    if n == 0: return 0     # base case 1
    if n == 1: return 1     # base case 2
    return fib(n-1) + fib(n-2)   # DO recursive calls

Forecast: fib(5) guess karo. Phir guess karo ki yeh tree factorial ki chain se taller hai ya wider.

Step 1 — DO base cases kyun? Har call n-1 aur n-2 mein split hoti hai. Agar hum sirf $0$ par ruke, toh n-2 branch fib(1) se seedha fib(-1) tak jaap sakta hai. Hum dono $0$ aur $1$ ko pakadne ki zaroorat hai. Yeh step kyun? Ek branching recursion neeche do directions se pahunch sakta hai, toh har ek ke liye ek stop chahiye.

Step 2 — Call tree draw karo. fib(5) fib(4) aur fib(3) mein split hota hai; unme se har ek phir split hota hai. Figure mein branching tree dekho — yeh fan out karta hai, factorial ki seedhi chain ke unlike. Yeh step kyun? Yeh tree-shaped recursion hai — woh shape jo recursion ko natural banati hai (dekho Tree and Graph Traversal).

Step 3 — Leaves se upar add karo. $F_{2} = 1, F_{3} = 2, F_{4} = 3, F_{5} = 5$ . Yeh step kyun? Leaves base cases hain; har internal node apne do bachon ka sum hai.

Verify: sequence $0, 1, 1, 2, 3, 5$ → fib(5) = 5. ✅ Dhyan do fib(3) do baar compute hota hai — woh wasteful overlap Fibonacci and overlapping subproblems aur Memoization and Dynamic Programming ko motivate karta hai.

Example 5 — Cell F: shrink-by-halving (chhoti depth)

Worked example Fast power:

power(2, 10) compute karo exponent ko halve karke

def power(base, e):
    if e == 0:                 # base case
        return 1
    half = power(base, e // 2) # EK call, exponent halved
    if e % 2 == 0:
        return half * half
    return half * half * base  # odd exponent: ek extra base

Forecast: e = 10 ke liye yeh kitne frames deep jaata hai? Guess karo — kya yeh 10 hai, ya kam?

Step 1 — Halve karo, decrement mat karo. Exponent girta hai e = 10 → 5 → 2 → 1 → 0. Har arrow ek recursive call hai, toh e = 0 par base fire hone se pehle 4 recursive calls hain. Outer power(2,10) call khud ko count karke, gehri jagah 5 frames alive hain (4 recursive calls + 1 original call). Yeh step kyun? "Recursive calls" count karta hai function ne khud ko kitni baar call kiya (arrows); "frames" count karta hai har active call ko pehli wali sameta jo aapne type ki. Frames = recursive calls + 1. Halving base tak lagbhag $⌊ lo g_{2} e ⌋$ recursive calls mein pahunchti hai, toh depth chhoti rehti hai. Shrink-by-one se compare karo, jisme $e$ recursive calls chahiye hote hain.

Step 2 — Even vs odd handle karo (saare cases!).

Even $e$ : $b^{e} = (b^{e /2})^{2}$ .
Odd $e$ : $b^{e} = (b^{e //2})^{2} \cdot b$ (integer division leftover 1 drop kar deta hai, toh hum ek extra base multiply karte hain). Yeh step kyun? Integer // remainder throw away karta hai, toh odd exponents base ka ek factor kho dete hain — hum ise wapas add karna chahiye.

Step 3 — power(2,10) trace karo. power(2,5) ko power(2,2) chahiye, jise power(2,1) chahiye, jise power(2,0)=1 chahiye. Build up: power(2,1)=1*1*2=2; power(2,2)=2*2=4; power(2,5)=4*4*2=32; power(2,10)=32*32=1024. Yeh step kyun? Har level square karta hai (aur kabhi kabhi ek base multiply karta hai), exactly even/odd rule se match karta hua.

Verify: $2^{10} = 1024$ . ✅ Recursive calls $= ⌊ lo g_{2} 10 ⌋ + 1 = 3 + 1 = 4$ — 10 se kaafi kam. ✅

Example 6 — Cell G: order matters (winding vs unwinding)

def up(n): if n < 0: return up(n-1) print(n) # call ke BAAD

Note: inme se har ek har frame mein exactly **ek** recursive call karta hai — yeh *linear* recursion hai, branching nahi. Sirf kaam ki *position* badlti hai.
**Forecast:** `down(3)` aur `up(3)` ke liye, padhne se pehle dono printed sequences predict karo.

**Step 1 — `down`: print winding ke dauran hota hai.**
`print(n)` recursive call se *pehle* run hota hai, toh yeh frames ke **neeche jaate waqt** fire karta hai: `3, 2, 1, 0`.
*Yeh step kyun?* Recursive call se pehle rakha kaam descent par execute hota hai.

**Step 2 — `up`: print unwinding ke dauran hota hai.**
`print(n)` sub-call ke poori tarah finish hone ke *baad* run hota hai, toh yeh frames ke **wapas pop hote waqt** fire karta hai: `0, 1, 2, 3`.
*Yeh step kyun?* Recursive call ke baad rakha kaam poore subtree ka wait karta hai, phir wapasi mein run hota hai — yeh exactly *post-order* [[Tree and Graph Traversal]] ka kaam karne ka tarika hai.

**Verify:** `down(3)` → `3,2,1,0`; `up(3)` → `0,1,2,3`. ✅ Same recursion, mirror-image output — sirf ek line ki position sab decide karti hai.

Example 7 — Cell H: real-world word problem

Worked example Russian dolls: ek stack mein kitni dolls nest hain yeh count karo

Ek doll ya toh solid hoti hai (andar kuch nahi) ya hollow hoti hai (exactly ek chhoti doll contain karti hai). Total dolls count karo.

def count_dolls(doll):
    if doll["inside"] is None:   # base case: solid doll
        return 1
    return 1 + count_dolls(doll["inside"])  # yeh doll + baaki

Forecast: 4 nested dolls ke stack ke liye, count aur frames ki number guess karo.

Step 1 — Story se base case identify karo. Sabse chhoti solid doll ke andar kuch nahi → yeh 1 count hoti hai, koi recursion nahi. Yeh step kyun? Har recursion ko "already known" answer chahiye; yahan woh sabse andar wali doll hai.

Step 2 — Recursive case identify karo. Ek hollow doll = khud (1) plus jo bhi count_dolls andar wali doll ke liye return karta hai. Yeh step kyun? Yeh self-similar rule hai: "baaki dolls" wahi problem hai, ek size chhoti (parent ke Russian-doll intuition se match karta hai).

Step 3 — 4 dolls trace karo. $1 + (1 + (1 + 1)) = 4$ . Yeh step kyun? Chaar frames pile up hote hain, sabse andar wala 1 return karta hai, aur har hollow doll wapsi mein 1 add karti hai.

Verify: total = 4, frames = 4. ✅ Units: dolls in = dolls counted.

Example 8 — Cell I: exam-style twist (bug spot karo)

Worked example Yeh "recursive sum"

None return karta hai. Bug dhundo.

def summ_buggy(L):
    if not L:
        return 0
    L[0] + summ_buggy(L[1:])   # <-- dhyan se dekho

Forecast: summ_buggy([4, 2, 7]) kya return karta hai? Trace karne se pehle guess karo.

Step 1 — Base case check karo. if not L: return 0 theek hai — empty list correctly 0 return karta hai. Yeh step kyun? Pehle usual suspect rule out karo; stop condition yahan sahi hai.

Step 2 — Recursive line inspect karo. L[0] + summ_buggy(L[1:]) ek value compute karta hai lekin koi return nahi hai. Python ise discard karta hai aur end se fall off karta hai → None return karta hai. Recursion sub-call ka result automatically wapas nahi bhejta; aapko explicitly return karna hoga (ya store karna hoga). Yeh step kyun? Jab base case 0 return karta hai, toh agla line upar L[0] + None try karta hai, jo khud TypeError raise karta — lekin single-element list ke liye buggy function cleanly None return karta hai kyunki uski recursive line ki value simply throw away ho jaati hai.

Step 3 — Fix karo.

def summ_fixed(L):
    if not L:
        return 0
    return L[0] + summ_fixed(L[1:])

Yeh step kyun? Ab combined value stack se wapas upar travel karti hai instead of throw away hone ke.

Verify: buggy version → None; fixed version → $4 + 2 + 7 = 13$ . ✅

Recall Matrix par quick self-test

fact(0) kaunsa cell hai? ::: Cell B — base case poora input hi hai, zero recursive calls. fib kaunse cell mein aayega aur do base cases kyun? ::: Cells D & E — branching recursion, aur n-2 branch 0 ko leap karke guzar sakta hai, toh hum 0 aur 1 dono pakadते hain. print ko recursive call ke baad move karne se woh kis phase mein run karta hai yeh badal jaata hai? ::: Winding (descent) se unwinding (return) mein, output order reverse ho jaata hai. Halving-power ko shrink-by-one se kaafi kam frames kyun chahiye? ::: Yeh base tak lagbhag log₂(e) recursive calls mein pahunchta hai instead of e ke.