Classic recursion — factorial, Fibonacci, binary search: Worked examples

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

Scenario matrix

Har recursion problem situations ke ek chhote grid mein kahin na kahin hoti hai. Agar koi walkthrough tumhe koi cell kabhi na dikhaye, toh jab woh aaye toh tum andaaze laga rahe hoge. Yeh hai woh poora grid jo hum cover karenge — har cell mein woh tricky cheez ka naam hai jo wahan galat ho sakti hai.

#	Machine	Scenario class	Tricky cheez
A	factorial	typical `n>0`	multiplications stack hoti hain, phir unwind hoti hain
B	factorial	boundary `n=0`	base case seedha fire karta hai, koi recursion nahi
C	factorial	invalid `n<0`	0 ke neeche koi base case nahi → infinite recursion
D	fibonacci	boundary `n=0, n=1`	do base cases, kyun do
E	fibonacci	typical `n≥2` naive	call tree branch karta hai aur kaam repeat karta hai
F	fibonacci	same `n` memoized	har subproblem ek baar compute hota hai
G	binary search	target present	halving index par converge karta hai
H	binary search	target absent	range collapse hoti hai (`lo>hi`) → `-1`
I	binary search	target edge par	pehla ya aakhri element, off-by-one ka khatre
J	binary search	unsorted input	"ek half phenko" logic invalid hai
K	word problem	real-world	phone-book / dictionary lookup as binary search

Neeche ke examples un cell(s) se tagged hain jo unhe hit karte hain. Saath milke yeh A–K ko touch karte hain.

Example 1 — factorial, typical case `n=4` (cell A)

Worked example

factorial(4) nikalo Pehle forecast karo: aage padhne se pehle andaaza lagao: kitne nested calls hote hain, aur final number kya hai?

Code yaad karo:

def factorial(n):
    if n == 0:                     # base case
        return 1
    return n * factorial(n - 1)    # recursive case

Step 1 — descend karo, calls ko stack par pile karo. Yeh step kyun? Har call apni multiplication tab tak finish nahi kar sakti jab tak chhoti call return na kare, isliye woh park ho jaati hai aur wait karti hai. $4! = 4 \cdot 3! = 4 \cdot (3 \cdot 2!) = 4 \cdot (3 \cdot (2 \cdot 1!)) = 4 \cdot (3 \cdot (2 \cdot (1 \cdot 0!)))$

Step 2 — base case hit karo. Yeh step kyun? n $4 \to 3 \to 2 \to 1 \to 0$ chala hai. n==0 par hum seedha 1 return karte hain — chain ruk jaati hai. Yeh sabse gehra point hai; figure ke neeche dekho.

Step 3 — unwind karo, upar aate waqt multiply karo. Yeh step kyun? Ab har parked call apne child ka answer receive karti hai aur apni ek multiplication karta hai: $0! = 1 \to 1 \cdot 1 = 1 \to 2 \cdot 1 = 2 \to 3 \cdot 2 = 6 \to 4 \cdot 6 = 24$

Answer: 24. (Nested calls: 4 recursive calls plus base, yani 5 frames deep.)

Verify: $4! = 4 \times 3 \times 2 \times 1 = 24$ . ✓ Plain definition se match karta hai.

Example 2 — factorial boundary `n=0` (cell B)

Example 3 — factorial invalid `n=-3` (cell C, degenerate)

Worked example

factorial(-3) kya karta hai? Forecast: kya yeh ek number return karta hai, ya crash karta hai? Kyun?

Step 1 — base case match karne ki koshish karo. Yeh step kyun? n = -3 ke saath if n == 0 False hai. Toh hum recurse karte hain: -3 * factorial(-4).

Step 2 — dekho n base se door bhaagtaa hai. Yeh step kyun? Agla call n = -4 hai, phir -5, -6, … Har ek 0 se aur door hai, paas nahi. Base case unreachable hai.

Step 3 — stack overflow ho jaata hai. Yeh step kyun? Frames hamesha ke liye pile hoti rahengi. Python recursion depth (~1000 by default) cap karta hai aur yeh raise karta hai:

RecursionError: maximum recursion depth exceeded

Answer: yeh RecursionError raise karta hai.

Verify (lesson): ek recursive case ko hamesha input ko base ki taraf move karna chahiye. Yahan $n - 1$ , $n < 0$ hone par $0$ se door move karta hai. Ek robust version input ko guard karta hai:

if n < 0:
    raise ValueError("factorial is undefined for negatives")

Yeh cell C ka point hai: input ki har direction ko terminate karna chahiye.

Example 4 — Fibonacci base cases `n=0, n=1` (cell D)

Worked example

fib(0) aur fib(1) nikalo Forecast: Fibonacci ek base case se kyun kaam nahi chala sakta jaise factorial ne chalaya?

Yaad karo:

def fib(n):
    if n < 2:                        # n=0 AUR n=1 dono cover karta hai
        return n
    return fib(n - 1) + fib(n - 2)

Step 1 — fib(0). 0 < 2 True hai, 0 return karo. Koi recursion nahi. Step 2 — fib(1). 1 < 2 True hai, 1 return karo. Koi recursion nahi.

Step 3 — kyun do values ki zaroorat hai. Yeh step kyun? Recursive case hai fib(n-1) + fib(n-2) — yeh do steps peeche jaata hai. Agar hum sirf fib(0) jaante, toh fib(1) compute karne ke liye fib(-1) chahiye hoga, jo kabhi terminate nahi karta. Toh humein do known answers pre-load karne padenge. Ek hi test n < 2 smartly n khud return karta hai, ek line mein $F_{0} = 0$ aur $F_{1} = 1$ deta hai.

Answers: fib(0)=0, fib(1)=1.

Verify: sequence $0, 1, 1, 2, 3, \dots$ se shuru hoti hai ✓

Example 5 — naive Fibonacci `fib(5)`, repeated work (cell E)

Worked example

fib(5) naively nikalo aur calls gino Forecast: answer ek chhota number hai, lekin andaaza lagao ki naive version kitne total calls karta hai.

Step 1 — recurrence expand karo. $F_{5} = F_{4} + F_{3}, F_{4} = F_{3} + F_{2}, F_{3} = F_{2} + F_{1}, F_{2} = F_{1} + F_{0}$

Step 2 — call tree banao. Yeh step kyun? Tree bimari expose karta hai: wohi subproblem unrelated branches mein appear hoti hai. Dekho fib(2) aur fib(1) kitni baar appear karte hain.

Step 3 — value padhlo. Leaves se unwind karke: $F_{2} = 1, F_{3} = 2, F_{4} = 3, F_{5} = 5$ .

Answer: fib(5) = 5.

Step 4 — calls gino. fib(n) ke liye calls ki sankhya $2 F_{n + 1} - 1$ hai. $n = 5$ ke liye: $2 F_{6} - 1 = 2 \cdot 8 - 1 = 15$ calls ek chhoti si number produce karne ke liye.

Verify: $F_{5} = 5$ (sequence $0, 1, 1, 2, 3, 5$ ). Call count $= 2 F_{6} - 1 = 15$ . ✓ Yeh exponential blow-up ( $Θ (φ^{n})$ ) woh trap hai jiske baare mein parent note ne warning di thi. Big-O Notation dekho.

Example 6 — memoized Fibonacci `fib(30)` (cell F)

Worked example

fib(30) memoization ke saath nikalo Forecast: naive fib(30) ~2.7 million calls karta hai. Cache ke saath, kitne distinct subproblems hain?

def fib(n, memo={}):
    if n < 2: return n
    if n in memo: return memo[n]
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

Step 1 — pehli baar jab bhi fib(k) maanga jaaye, compute karo aur store karo. Yeh step kyun? Cache memo answers yaad rakhta hai. Jo pehli branch fib(k) maangti hai woh use compute karti hai; baad ki har branch use instantly padhti hai.

Step 2 — distinct subproblems gino. Yeh step kyun? Subproblems exactly fib(0), fib(1), …, fib(30) hain — yeh 31 distinct values hain, har ek ek baar → $Θ (n)$ instead of $Θ (φ^{n})$ .

Step 3 — value. $F_{30} = 832040$ .

Answer: fib(30) = 832040.

Verify: $F_{30} = 832040$ (VERIFY mein check kiya gaya). Memoization and Dynamic Programming dekho ki cache tree ko line mein kyun badal deta hai.

Example 7 — binary search, target present (cell G)

Worked example

[2, 5, 8, 12, 16, 23, 38, 56, 72, 91] mein target = 23 dhundo Forecast: list mein 10 items hain. Maximum comparisons ka andaaza lagao ( $⌈ lo g_{2} 10 ⌉ = ?$ ).

def binary_search(arr, target, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo > hi: return -1
    mid = (lo + hi) // 2
    if arr[mid] == target: return mid
    elif arr[mid] < target: return binary_search(arr, target, mid+1, hi)
    else:                    return binary_search(arr, target, lo, mid-1)

Step 1 — middle probe karo, ek half phenko. Yeh step kyun? Sorted list par, middle se compare karne par pata chalta hai ki kaunsa half target contain nahi kar sakta, toh tum use discard karte ho. Figure mein shrinking window follow karo.

call	lo	hi	mid	arr[mid]	decision (Kyun?)
1	0	9	4	16	$16 < 23$ → right jao, `lo=5`
2	5	9	7	56	$56 > 23$ → left jao, `hi=6`
3	5	6	5	23	mila → `5` return karo

Answer: index 5. 3 comparisons liye (aur $⌈ lo g_{2} 10 ⌉ = 4$ worst case hai, toh 3 bound ke andar hai).

Verify: arr[5] == 23. ✓

Example 8 — binary search, target absent (cell H, degenerate collapse)

Worked example

[2, 5, 8, 12, 16, 23, 38, 56, 72, 91] mein target = 40 dhundo Forecast: 40 list mein nahi hai. Recursion kaise jaanti hai kab rukna hai, aur kya return karta hai?

Step 1 — usual tarah narrow karo.

call	lo	hi	mid	arr[mid]	decision
1	0	9	4	16	$16 < 40$ → `lo=5`
2	5	9	7	56	$56 > 40$ → `hi=6`
3	5	6	5	23	$23 < 40$ → `lo=6`
4	6	6	6	38	$38 < 40$ → `lo=7`

Step 2 — range collapse ho jaata hai. Yeh step kyun? Ab lo=7, hi=6, toh lo > hi True hai. Window empty hai — koi jagah nahi bachi jahan target chhup sakta ho. Yeh "not found" ka base case hai.

Answer: -1.

Verify: 40 genuinely array mein nahi hai, aur lo > hi sahi se empty range signal karta hai. ✓ Yeh dikhata hai ki absent path hamesha terminate karta hai: har step hi - lo shrink karta hai, toh empty case tak zaroor pahunchega.

Example 9 — binary search edges par (cell I, off-by-one)

Worked example

target = 2 (pehla element) aur target = 91 (aakhri element) dhundo Forecast: off-by-one bugs ends par rehte hain. Kya code index 0 aur index 9 sahi se reach karta hai?

2 dhundo (leftmost):

call	hi	mid	arr[mid]	decision
1	9	4	16	$16 > 2$ → `hi=3`
2	3	1	5	$5 > 2$ → `hi=0`
3	0	0	2	mila → `0` return karo

91 dhundo (rightmost):

call	lo	hi	mid	arr[mid]	decision
1	0	9	4	16	$16 < 91$ → `lo=5`
2	5	9	7	56	$56 < 91$ → `lo=8`
3	8	9	8	72	$72 < 91$ → `lo=9`
4	9	9	9	91	mila → `9` return karo

Answers: 2 → index 0; 91 → index 9.

Edges safe kyun hain: mid+1 aur mid-1 moves guarantee karte hain ki lo aur hi exactly index 0 aur 9 par land karte hain. Agar code ne mid±1 ki jagah mid use kiya hota, toh yeh ek one-element window par forever loop kar sakta tha — yeh wahi classic off-by-one bug hai jise yeh example rule out karta hai.

Verify: arr[0]==2 aur arr[9]==91. ✓

Example 10 — binary search UNSORTED input par (cell J, invalid precondition)

Worked example

[38, 2, 91, 8, 16, 5] (sorted NAHI hai) mein target = 8 dhundo Forecast: value 8 present hai (index 3 par). Kya binary search use dhoondh paayega?

Step 1 — middle blindly probe karo.

call	lo	hi	mid	arr[mid]	decision (invalid!)
1	0	5	2	91	$91 > 8$ → left jao, `hi=1`
2	0	1	0	38	$38 > 8$ → left jao, `hi=-1`

Step 2 — range "not found" par collapse ho jaata hai. Yeh kyun fail karta hai: algorithm assume karta hai ki mid ke left mein sab chhota hai. Yahan yeh galat hai — 8 index 3 par hai, mid=2 ke right mein, lekin comparison $91 > 8$ ne ise right half discard karne par trick kar diya. Yeh kabhi wahaan dekhta hi nahi jahaan answer hai.

Answer: -1 — GALAT. Sahi index 3 hai.

Verify: 8 diye gaye list mein index 3 par hai, phir bhi binary search -1 return karta hai. ✓ (bug real hai). Fix: pehle sort karo (dekho Sorting Algorithms), jisme $Θ (n lo g n)$ lagta hai, ya linear search use karo. Yeh exactly parent note ka steel-man trap hai.

Example 11 — real-world word problem (cell K)

Worked example Phone-book lookup

Ek physical phone book mein 1,000,000 sorted names hain. Tumhara dost linear search use karta hai (shuru se page by page). Tum binary search use karte ho (middle kholo, aadha phenko, repeat karo). Worst case mein, tumhe dono mein kitne "opens" chahiye?

Forecast: compute karne se pehle dono numbers ka andaaza lagao.

Step 1 — linear search worst case. Kyun: agar naam last page par hai, toh tum sab million check karte ho. $comparisons_{linear} = 1, 000, 000$

Step 2 — binary search worst case. Kyun: har open baaki ko half kar deta hai: $1, 000, 000 \to 500, 000 \to \dots \to 1$ . Halvings ki sankhya $⌈ lo g_{2} 1, 000, 000 ⌉$ hai. $lo g_{2} 1, 000, 000 \approx 19.93 \Rightarrow 20 opens$

Answer: linear = 1,000,000 opens; binary = 20 opens.

Verify: $2^{20} = 1, 048, 576 \geq 1, 000, 000 > 2^{19} = 524, 288$ , toh $⌈ lo g_{2} 1 0^{6} ⌉ = 20$ . ✓ Yeh 50,000× speed-up hai jo "logarithmic" feel karta hai — dekho Divide and Conquer aur Recursion vs Iteration.

Recall Matrix par quick self-test

factorial(-2) kya karta hai, aur kyun? ::: RecursionError raise karta hai — n-1, base case 0 se door move karta hai, isliye kabhi terminate nahi karta. Fibonacci ko do base cases kyun chahiye lekin factorial ko ek? ::: fib do steps peeche jaata hai (n-1 aur n-2), isliye do known starting values chahiye warna 0 ke neeche recurse karta hai. Binary search kya return karta hai, aur missing target kaise detect karta hai? ::: -1, detect hota hai jab range lo > hi par collapse ho jaati hai (empty window). Binary search ne kisi aise value ke liye -1 return kiya jo tumhe pata hai present hai — likely cause? ::: Array sorted nahi tha; halving logic unsorted data par invalid hai. 1,000,000 sorted items par binary search ke worst-case comparisons? ::: 20 (1,000,000 ka log base 2 ka ceil).

Connections

Classic recursion — factorial, Fibonacci, binary search (index 1.2.38) — woh parent jise yeh deep-dive expand karta hai
Big-O Notation — jahaan se $Θ (n)$ , $Θ (lo g n)$ , $Θ (φ^{n})$ aate hain
Memoization and Dynamic Programming — Example 6 ka cache
Divide and Conquer — binary search aur phone book
Recursion vs Iteration — inhe traces ke peeche trade-offs
The Call Stack and Stack Frames — Examples 1 aur 3 mein pile-and-unwind
Sorting Algorithms — unsorted-input trap ka fix