Classic recursion — factorial, Fibonacci, binary search: Visual walkthrough

1.2.38 · D2 · Coding › Introduction to Programming (Python) › Classic recursion — factorial, Fibonacci, binary search

Hume sirf kuch ideas chahiye, aur hum har ek ko use karne se pehle earn karenge. Chalte hain ekdum zero se.

Definition Do counting symbols jo hum baar baar use karenge

$c$ ::= ek fixed amount of "ek step" ka work — jaise, ek single comparison ya ek single multiplication karna. Yeh input ke saath nahi badhta; yeh bas "ek chhota chunk of effort" hai. Hum $c$ likhte hain nanoseconds ki specific number ki jagah kyunki exact number matter nahi karta — sirf yeh matter karta hai ki total kaise badhta hai.
$Θ (\cdot)$ (padho "Theta of") ::= ==ek label jo batata hai ki total work kitni tezi se badhti hai jab input $n$ bada hota hai==, constant multipliers ko ignore karke. $Θ (n)$ matlab "work $n$ ke proportion mein badhti hai" ( $n$ double karo, roughly work double). $Θ (lo g n)$ matlab "work us number ki tarah badhti hai kitni baar tum $n$ ko half kar sakte ho". $Θ (φ^{n})$ matlab "work har baar $n$ mein ek badhne par roughly $φ$ se multiply hoti hai" — explosive. Full treatment in Big-O Notation.

YEH DO KYUN. Recurrences jaise $T (n) = T (n - 1) + c$ literally kehte hain "size $n$ ka work, size $n - 1$ ka work hai plus ek chhota chunk $c$ ." $Θ$ woh hai jisse hum us sentence ko growth rate mein convert karte hain.

Step 1 — "Khud ko ek chhote problem par call karna" actually kaisa dikhta hai

KYA. Ek function ek named machine hai: tum ise ek input do, yeh ek output deta hai. Jab hum $factorial (3)$ likhte hain toh matlab hai "factorial machine ko andar number $3$ ke saath run karo".

EK CHHOTI COPY KYUN. Parent ne jo definition di woh dekho: $answer jo chahiye n! = current number n \times WAHI sawaal, ek size chhota (n - 1)!$ Term by term: $n!$ woh hai jo hum compute karna chahte hain; $n$ woh number hai jo abhi hamare paas hai; aur $(n - 1)!$ bilkul wahi sawaal hai jo ek chhote number ke baare mein pucha gaya. Woh last piece hi poora trick hai — problem mein khud ka ek shrunk copy hai.

PICTURE. Neeche, har machine ek rounded box hai. Ek box tab tak finish nahi ho sakta jab tak uske andar ka chhota box finish nahi hota. Boxes Russian dolls ki tarah nest karte hain, $3 \to 2 \to 1 \to 0$ tak shrink karte hue, jab tak sabse chhoti doll ( $0$ ) ko kisi help ki zaroorat nahi hoti.

Figure — Classic recursion — factorial, Fibonacci, binary search

Step 2 — Stack NEECHE jaate hue bharta hai

KYA. Jab $factorial (3)$ ko $factorial (2)$ chahiye, woh khud ko pause karta hai aur ek note likhta hai: "Mujhe abhi bhi $3$ se multiply karna hai jab answer wapas aayega." Woh note ek stack frame hai — ek chhota memory box jo machine rakhti hai.

YEH PAUSE KYUN KARNA PADTA HAI. Multiplication $3 \times (\dots)$ abhi nahi ho sakti, kyunki $(\dots)$ abhi pata nahi. Toh machine half-done work park karti hai aur aur gehri dive karta hai. Har dive ek frame add karti hai.

PICTURE. Tower ko top-to-bottom padho. Har nayi call ek frame neeche add karti hai (yahi woh "piling up" hai jo parent ne mention kiya tha). Har frame ke right side mein pending work likha hua notice karo — wahi wait kar raha hai.

$factorial (3) \Rightarrow factorial (2) \Rightarrow factorial (1) \Rightarrow base case, aur gehri dive nahi factorial (0)$

Har $\Rightarrow$ matlab hai "maine pause kiya aur ek chhote mujhse pucha". Chain rukti hai jaise hi $0$ tak pahunchti hai.

Step 3 — Stack UPAR jaate hue khaali hota hai (the unwind)

KYA. Base case $factorial (0)$ turant $1$ return karta hai. Ab parked frames bottom-first jaag uthte hain, har ek apna ek waiting multiplication karta hai.

BOTTOM-FIRST KYUN. Woh frame jo sabse last mein add hua woh wala hai jiska chhota sawaal sabse pehle answer hua, toh woh pehle resume karta hai. Isi liye exactly ek stack use hota hai: last in, first out.

PICTURE. Wahi tower jo Step 2 mein tha, ab green return arrows ke saath bottom-to-top padho. Dekho kaise number $1$ upar travel karta hai, har floor par multiply hota hua: $1 \to 1 \times 1 \to 2 \times 1 \to 3 \times 2$ .

$0! 1 \times 1 1! 1 \times 2 2! 2 \times 3 3! 6$

Har labelled brace woh value hai jo ek floor return karta hai; har arrow woh multiplication hai jo woh floor wait kar raha tha karne ke liye. Final $6$ hai $3!$ .

Recall Factorial

$Θ (n)$ kyun cost karta hai Iska recurrence hai $T (n) = T (n - 1) + c$ : " $n$ ka work equals $n - 1$ ka work plus ek chunk $c$ (ek single multiply)." Tower mein $n$ se $0$ tak har number ke liye ek floor hai: woh hai $n + 1$ floors, har ek $c$ cost karta hai. $c$ itni baar add karne se $(n + 1) \cdot c$ milta hai, jo $n$ ke saath step mein badhta hai → $Θ (n)$ . Dekho Big-O Notation.

Step 4 — Fibonacci: woh box jo DO boxes kholti hai

KYA. Factorial ne ek chhota box khola. Fibonacci ka rule do kholta hai: $F_{n} = ek step peeche F_{n - 1} + do step peeche F_{n - 2}$ $F_{n}$ woh number hai jo chahiye; $F_{n - 1}$ aur $F_{n - 2}$ woh do chhote sawaal hain jo hume poochne padenge. Kyunki rule do steps peeche jaata hai, hume do base cases chahiye ( $F_{0} = 0$ , $F_{1} = 1$ ) — warna ek branch $F_{0}$ se neeche gir jaayegi aur kabhi land nahi karegi.

YEH EK TREE KYUN BANATA HAI, TOWER NAHI. Ek box jo do boxes spawn kare, jo har ek do aur spawn kare, woh seedhi line nahi hai — woh branch karta hai. Wahi branching saari mushkil ka source hai.

PICTURE. $F_{4}$ ke liye call tree. Har node par split follow karo. $F_{2}$ label wale do nodes circle karo: unhe alag branches mein compute kiya jaata hai jo kabhi ek doosre se baat nahi karte.

Step 5 — Naive tree slow kyun hai (the $φ^{n}$ derivation)

KYA. $C (n)$ ko naive $fib (n)$ ke calls ki number maano. $fib (n)$ (for $n \geq 2$ ) ka har call exactly $fib (n - 1)$ ke calls plus $fib (n - 2)$ ke calls karta hai, plus khud: $calls for n C (n) = left branch C (n - 1) + right branch C (n - 2) + yeh call khud 1$ Yeh same shape hai Fibonacci recurrence ki tarah — calls ki count Fibonacci numbers ki tarah badhti hai.

$φ^{n}$ KYUN BADHTA HAI, $2^{n}$ NAHI. Agar har box do full-size boxes kholti, toh count har level par double hota → $2^{n}$ . Lekin aisa hota nahi: ek branch size $n - 1$ ki hai aur doosri sirf $n - 2$ ki — doosri branch chhoti hai, toh tree lopsided hai, full doubling nahi. Sacchi growth rate woh number $φ$ hai jo sequence ke apne multiply-rule ko satisfy karta hai: $φ^{2} = φ + 1 ⟹ φ = \frac{1 + 5}{2} \approx 1.618$ Term by term: $φ^{2}$ hai "do steps of growth", aur woh equals hai " $φ$ (ek step) plus $1$ " — exactly wahi reach-back-one-and-two pattern. Toh $n$ mein ek ka har increase work ko roughly $φ \approx 1.618$ se multiply karta hai ( $2$ se nahi), giving $Θ (φ^{n})$ . Doubling se slower, lekin phir bhi explosive.

PICTURE. Wahi tree, ab repeated subtrees same colour se paint ki hui. Kisi bhi colour ki har extra copy pure wasted recomputation hai — aur kisi bhi node ke neeche dono branches visibly unequal height ki hain, isi liye base $φ$ hai aur $2$ nahi.

Step 6 — Memoization: duplicates ko cross out karo

KYA. Ek notebook (memo) rakho jo " $k$ " → " $F_{k}$ " map kare. $F_{k}$ compute karne se pehle, notebook mein dekho. Agar wahan hai, turant wapas do; agar nahi, ek baar compute karo aur likh lo.

YEH TREE KYUN COLLAPSE KARTA HAI. Pehli baar $F_{2}$ solve karne ke baad, har doosra $F_{2}$ node ek instant lookup ban jaata hai — uska poora subtree delete ho jaata hai. Branching tree ek slim path mein flatten ho jaati hai.

PICTURE. $F_{4}$ tree jisme duplicate subtrees cross out hain aur "cache hit" tag se replace hain. Jo bacha woh ek thin chain hai — sirf $n$ genuine computations.

$naive: Θ (φ^{n}) notebook memoized: Θ (n)$

Arrow padho: "notebook add karna exponential ko linear mein badal deta hai."

Step 7 — Binary search: ek baar mein aadhi picture phenk dena

KYA. Ek sorted list di gayi hai, hum target ko middle element se compare karte hain aur woh half discard karte hain jisme woh ho nahi sakta. lo aur hi woh region ke left aur right edges hain jo abhi bhi play mein hain; mid hai middle index $⌊(lo + hi) /2 ⌋$ .

MIDDLE KYUN, AUR SORTED KYUN. Ek sorted list mein, mid ke left ka sab kuch chhota hai aur right ka sab kuch bada. Toh middle par ek comparison safely poore half ko rule out kar deta hai — lekin sirf isliye kyunki order guarantee karta hai. Unsorted data par "aadha throw away" logic ek jhooth hai.

PICTURE. List $[1, 3, 5, 7, 9, 11]$ mein $7$ search karna. Teen shrinking bars: greyed-out region woh half hai jo throw away kiya; highlighted region woh hai jo bacha; arrow har round mein mid mark karta hai. Round 1 middle value $5$ check karta hai; $5 < 7$ kyunki hum right half rakhte hain. Round 2 $9$ check karta hai; $9 > 7$ kyunki hum left half rakhte hain. Round 3 exactly $7$ par land karta hai aur uska index $3$ return karta hai. Picture left-to-right, top-to-bottom padho — har number aur decision uspar drawn hai.

$Θ (lo g n)$ KYUN. Iska recurrence hai $T (n) = T (n /2) + c$ : " $n$ items ka work equals unke half ka work, plus ek chunk $c$ (single middle comparison)." $n$ se start karke repeatedly half karte hue — $n, \frac{n}{2}, \frac{n}{4}, \dots, 1$ — lagbhag $lo g_{2} n$ halvings lagte hain, har ek $c$ cost karta hai. Toh total hai lagbhag $(lo g_{2} n) \cdot c$ → $Θ (lo g n)$ .

Step 8 — Edge cases jinhe kabhi miss nahi karna chahiye

KYA & KYUN. Har recursion mein quiet corners hote hain. Unhe draw karo taaki koi reader kabhi surprised na ho:

factorial(0) — base case turant fire hota hai, $1$ return karta hai. Koi dive nahi. (Sabse chhota problem directly answer.)
fib(0) aur fib(1) — dono base cases; agar missing hote toh koi bhi $F_{0}$ se neeche recurse karta.
Binary search, target absent (e.g. $8$ ): region tab tak half hota rehta hai jab tak lo > hi — ek empty range. Woh "not found" base case hai; woh $- 1$ return karta hai.
Binary search on an empty list: hi = len(arr)-1 = -1, toh lo(0) > hi(-1) pehli call par hi true hai → zero comparisons ke saath $- 1$ return karta hai.

PICTURE. "Target absent" path: lo aur hi cross over karte hain, koi bars highlighted nahi — woh moment jab recursion "not found" ke saath rukti hai.

Ek-picture summary

Teeno recursions ek canvas par: factorial ka seedha tower (har step $- 1$ , cost $Θ (n)$ ), Fibonacci ka branching tree notebook se collapse hua, aur binary search ki halving bars (cost $Θ (lo g n)$ ). Teen silhouettes — ek seedha column, ek lopsided tree, aur shrinking bars — poora page ek nazar mein.

Recall Feynman: plain words mein poora walkthrough

Recursion ek stack of paused workers hai. Factorial: worker $3$ tab tak finish nahi kar sakta jab tak worker $2$ finish nahi karta, jo worker $1$ ka wait karta hai, jo worker $0$ ka wait karta hai — woh akela jo seedha answer jaanta hai. Worker $0$ kehta hai " $1$ ", aur answer upar climb karta hai, har floor par multiply hota: $1, 1, 2, 6$ . Fibonacci same karta hai lekin har worker do helpers ko call karta hai, toh agar koi kuch nahi likhta toh wahi chhote sawaal mountain of times dobara pooche jaate hain — unhe ek notebook mein likh lo aur mountain flatten ho jaata hai. Binary search ek worker hai jo sorted phone book mein dekh raha hai: middle kholो, woh half throw away karo jisme tumhara naam nahi ho sakta, repeat karo. Har glance book ka aadha delete karta hai, toh tum lagbhag $lo g_{2} n$ glances mein done ho. Jab book mein throw away karne ke liye kuch nahi bachta, naam wahan tha hi nahi.

Connections

Recursion vs Iteration — tower aur halving pictures loops ban jaate hain
Big-O Notation — $Θ (n)$ , $Θ (φ^{n})$ , $Θ (lo g n)$ kahan se aate hain
Memoization and Dynamic Programming — Step 6 mein notebook
Divide and Conquer — binary search halving picture hai
The Call Stack and Stack Frames — Steps 2–3 mein towers
Sorting Algorithms — binary search ka precondition