Visual walkthrough — Recursion — call stack visualization, base case, recursive case

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

Kuch bhi shuru karne se pehle, teen plain words jo hum poore page mein use karenge:

Humara target, ek baar clearly bola gaya taaki neeche ka har symbol earned lage:

Step 1 — Self-similar shape dhundho

KYA. Product ko dekho aur last number, $n$, ko peel karo: $n!=\underset{\text{the biggest factor}}{\underbrace{n}}\cdot \underset{\text{this is just }(n-1)!}{\underbrace{(1\cdot 2\cdots (n-1))}}.$ Toh $n!=n\cdot (n-1)!$. Term $(n-1)!$ ka matlab hai "wohi factorial question, lekin ek size chota".

KYUN. Recursion tabhi kaam aati hai jab ek bada problem apne andar ek chota copy contain karta ho. Yahan copy literally andar baithi hai: $n!$ jaanne ke liye tumhe sirf $n$ aur $(n-1)!$ ka answer chahiye. Woh embedded copy hi recursive case hai.

PICTURE. Neeche nested boxes: outer box $n!$ hai; label $n$ peel karne par ek identical-shaped inner box $(n-1)!$ dikhta hai, aur aise aage andar jaate jaate.

Step 2 — Woh floor dhundho jahan shrinking rukti hai

KYA. Peeling karte raho: $n!\to (n-1)!\to (n-2)!\to \cdots \to 1!\to 0!$. Aur $0!$ ko hum simply define karte hain $1$ ke barabar (empty product — kuch bhi multiply nahi, "do-nothing" number $1$ milta hai). $\text{fact}(0)=1\text{(no multiplication, no further call)}.$

KYUN. Ek recursive machine jo sirf shrink karti rahe woh hamesha ke liye girती rahegi. Humein ek aisa input chahiye jiska answer seedha pata ho, zero further recursion ke saath. Yahi base case hai. $0$ choose karna ($1$ nahi) input $\text{fact}(0)$ ko bhi free mein correctly handle kar leta hai.

PICTURE. Descending staircase: har step input ko ek se giraata hai; base case $0!=1$ woh solid ground hai jis par staircase land karti hai.

Step 3 — Do-case rule likho

KYA. Steps 1 aur 2 ko ek definition mein glue karo. Brace ka matlab hai "woh line choose karo jiska condition true ho": $\text{fact}(n)=\{\begin{array}{ll}1& n=0(\text{base case})\\ \underset{\text{this call’s own }n}{\underbrace{n}}\cdot \underset{\text{smaller sub-problem}}{\underbrace{\text{fact}(n-1)}}& n>0(\text{recursive case})\end{array}$

KYUN. Har recursive function ko exactly yeh do parts chahiye: ek stop (base case) aur ek shrink-and-combine (recursive case). $n-1$ base ki taraf progress guarantee karta hai; $n\cdot$ woh "combine" hai jo answer ko reassemble karta hai.

PICTURE. Ek fork-in-the-road: diamond n == 0 test karta hai; ek branch $1$ return karta hai, doosra multiply karta hai aur ek chota self call karta hai.

def fact(n):
    if n == 0:            # base case  → the STOP
        return 1
    return n * fact(n-1)  # recursive case → shrink & combine

Step 4 — Winding: frames ko pile up hote dekho

KYA. fact(3) call karo. Yeh finish nahi ho sakta, kyunki ise pehle fact(2) chahiye — toh yeh pause karta hai aur ek naya frame push hota hai. Uss wale ko fact(1) chahiye, pause, push. Aur aise aage: $\text{fact}(3)=3\cdot \boxed{\text{fact}(2)},\text{fact}(2)=2\cdot \boxed{\text{fact}(1)},\text{fact}(1)=1\cdot \boxed{\text{fact}(0)}.$ Har boxed part ek abhi-tak-unknown answer hai jiska paused call wait kar raha hai.

KYUN. Ek call tabhi return kar sakti hai jab uska sub-call answer de. Toh poori chain neeche jaate hue freeze ho jaati hai — yeh descent winding phase hai. Importantly, har frame apna own private $n$ rakhta hai ($n=3$ wala frame aur $n=2$ wala frame saath exist karte hain — yeh shared nahi hain).

PICTURE. Chaar sticky-notes stacked, top = most recent (fact(0)), har note apna private $n$ aur upar wali note ki taraf "waiting for ..." arrow dikhata hai.

Step 5 — Base case land karta hai

KYA. Top frame fact(0) hai. Yeh n == 0 match karta hai, toh yeh $1$ immediately return karta hai — koi naya frame nahi, koi multiplication nahi. $\text{fact}(0)⟶1.$

KYUN. Yeh ek akeela moment hai jahan recursion thin air se value produce karti hai. Is line ke bina pile Python ke depth limit (~1000) ke baad bhi badhti rahegi aur RecursionError se crash kar degi. Base case winding aur unwinding ke beech ka hinge hai.

PICTURE. Top sticky-note flip hoti hai aur green "1" reveal hoti hai, poore pile mein pehli concrete value.

Step 6 — Unwinding: wapas upar jaate hue multiply karo

KYA. Ab top se notes peel karo (LIFO) aur har ek ko uski paused multiplication finish karne do, upar se milne wale answer ka use karke: $\text{fact}(1)=1\cdot \underset{\text{from fact(0)}}{\underbrace{1}}=1,\text{fact}(2)=2\cdot \underset{\text{from fact(1)}}{\underbrace{1}}=2,\text{fact}(3)=3\cdot \underset{\text{from fact(2)}}{\underbrace{2}}=6.$

KYUN. Kyunki sabse gehri (last-pushed) frame pehle finish hoti hai, multiplications outside-in on the way up hoti hain — yeh ordering LIFO se force hoti hai, humari choice se nahi. fact(3) last mein complete hota hai aur final $6$ deliver karta hai.

PICTURE. Stack neeche shrink ho raha hai, ek value $1\to 1\to 2\to 6$ hand-over-hand climb karti hai jaise har frame pop hota hai.

Step 7 — Degenerate aur edge inputs

KYA aur KYUN, case by case:

• $\text{fact}(0)$ — sabse chota legal input. Pehli hi call mein base case hit hota hai. Pehle frame ke baad zero frames stack hote hain; answer $1$ instantly return hota hai. Isliye humne $0$ choose kiya ($1$ nahi) base ke liye — function bina kisi special-casing ke apne floor par correct hai.
• $\text{fact}(1)$ — floor ke ek step upar. fact(0) tak ek baar winds karta hai, ek baar unwinds: $1\cdot 1=1$. ✅ (Sahi: $1!=1$.)
• $\text{fact}(\text{negative})$ — woh trap. fact(-1) try karo: yeh $>0$ hai? Nahi. Kya yeh $=0$ hai? Nahi. Toh yeh base case skip karta hai aur fact(-2) call karta hai, phir fact(-3), … hamesha ke liye. Pile overflow ho jaata hai → RecursionError. Lesson: tumhara base case har woh path catch karna chahiye jo shrinking le ja sakti hai. Ek safer guard hai if n <= 0: return 1.

PICTURE. Teen mini-stacks side by side: fact(0) (ek note, instant), fact(1) (do notes), aur fact(-1) (ek hamesha barhta red tower jo ceiling ke through crash karta hai).

Ek-picture summary

Poori kahaani ek V-shape mein: left arm se neeche frames wind karte hain (har ek pausing, har ek apna $n$ rakhte hue), base case $0!\to 1$ V ke bottom par baitha hai, aur right arm se upar unwind karte hain, $1\to 1\to 2\to 6$ multiply karte hue.

Active recall

Related: Iteration — for and while loops · Fibonacci and overlapping subproblems · Big-O and Recursion Depth · Memoization and Dynamic Programming · Tree and Graph Traversal