Classic recursion — factorial, Fibonacci, binary search: Question bank

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

Intuition Is page ko kaise use karein

Yeh parent topic ke liye ek concept gym hai. Neeche har item kisi misconception ya boundary case ko target karta hai — arithmetic ko nahi. Prompt padho, apna jawab ek reason ke saath zor se bolo, phir reveal karo. Agar tumhara jawab sirf "haan/nahi" tha bina kyun ke, toh tumne abhi sach mein samjha nahi hai.

Shuru karne se pehle, woh words jis par questions lean karte hain unhe plain language mein re-anchor karte hain:

Base case = woh input jo itni choti ho ki jawab obvious ho aur aage koi recursion ki zaroorat na ho. Yeh woh floor hai jo girne ko rok deta hai.
Recursive case = function ka khud ko ek chote input par call karna aur result ko joddna.
Call stack = computer ka hidden "unfinished jobs" ka pile — ek box (stack frame) har pending call ke liye, chhoti call ka jawab upar aane ka intezaar karte hue.

Yeh mnemonic yaad rakho: "Base, Break, Believe."

Pehle, teen symbols jo yeh page use karta hai (inhe pehle samjho phir aage bado)

Kuch baad ke answers mein $Θ (g^{n})$ jaise cheezein hain (kisi growth base $g$ ke liye jo hum pin down karenge) ya $T (n) = T (n /2) + c$ . Agar yeh alien runes lagte hain, toh yeh section ek baar padho — phir poora page self-contained hai.

Sach ya jhooth — justify karo

Ek well-defined recursive algorithm ko har valid input ke liye terminate karna chahiye, sirf kuch ke liye nahi.

Sach. "Kuch inputs ke liye terminate hota hai" kaafi nahi — ek correct algorithm ko sabhi valid inputs par base case tak pahunchna chahiye. Agar ek bhi valid input infinitely recurse kare, toh algorithm toot gayi; "chota" step ko har baar provably base ki taraf badhna chahiye.

Factorial ka base case

1! = 1

bhi ho sakta hai

0! = 1

ki jagah aur

n \geq 1

ke liye kaam karega.

n \geq 1

ke liye Sach, lekin yeh factorial(0) par toot jaata hai — woh call factorial(-1) par recurse karti aur kabhi nahi rukti.

0! = 1

use karna ek aur input ko safely cover karta hai, isliye yeh preferred hai.

fib sirf ek base case ke saath (if n == 0: return 0) kaam karta hai.

Jhooth. fib(1) compute karega fib(0) + fib(-1), aur fib(-1) zero se neeche forever recurse karega. Recurrence do steps peeche jaati hai, isliye do known values chahiye.

Naive recursive Fibonacci galat answers deta hai kyunki woh slow hai.

Jhooth. Yeh bilkul sahi answers deta hai — yeh sirf wasteful hai, same subproblems ko exponentially recompute karta hai. Slowness aur incorrectness alag failures hain; yahan sirf speed galat hai.

Binary search duplicates hone par target ka sabse chota index return karta hai.

Jhooth (jaisa likha hai). Middle-first logic kisi bhi matching copy par land kar sakta hai; yeh koi ek valid index return karta hai, guaranteed leftmost nahi. Pehla occurrence dhundne ke liye "keep searching left" ka extra tweak chahiye.

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

Sach — dekho Recursion vs Iteration. Kisi bhi recursion ko explicit stack aur loop ke saath simulate kiya ja sakta hai; machine pehle se hi apne call stack ke saath aisa karta hai.

Factorial ko memoize karna Fibonacci ko memoize karne jaisi hi speedup deta hai.

Jhooth. Factorial ke calls kabhi bhi ek subproblem repeat nahi karte — factorial(n) exactly ek baar factorial(n-1) call karta hai — toh caching zero benefit ke saath overhead add karta hai. Fibonacci subproblems repeat karta hai, isliye memoization uski madad karta hai.

Unsorted list par binary search hamesha

- 1

return karta hai.

Jhooth. Yeh ek galat index return kar sakta hai ya present element miss kar sakta hai — "ek half throw away karo" logic unsorted data par simply invalid hai, isliye results unreliable hain, uniformly

- 1

nahi.

Fibonacci call tree — $Θ (φ^{n})$ kyun, dekho aur derive karo

Formula Characteristic-equation derivation (apne base cases ke saath)

Maano $C (n)$ = fib(n) evaluate karne mein ki gayi fib calls ki total sankhya. Pehle initial conditions state karo, kyunki ek recurrence unke bina meaningless hai: base-case calls fib(0) aur fib(1) mein se har ek exactly ek call karti hai (khud ko, koi recursion nahi), toh $C (0) = 1, C (1) = 1.$ $n \geq 2$ ke liye, fib(n) evaluate karna ek call hai khud ke liye plus jo do children karti hain woh saari calls: $C (n) = yeh call 1 + C (n - 1) + C (n - 2) .$ Ab, growth-rate question ke liye $+ 1$ kyun drop kar sakte hain. Homogeneous part $C (n) = C (n - 1) + C (n - 2)$ pehle se exponentially badhta hai; extra $+ 1$ per node zyada se zyada nodes ki sankhya ke proportional total add karta hai, jo khud usi exponential order ka hai. Usi order (ya chote) ki quantity add karna exponential base kabhi nahi badalta — yeh sirf ek constant factor se rescale karta hai, aur $Θ (\cdot)$ constant factors ignore karta hai. Toh base purely homogeneous recurrence se decide hota hai. Ek solution $C (n) = x^{n}$ guess karo aur plug in karo: $x^{n} = x^{n - 1} + x^{n - 2} .$ $x^{n - 2}$ se divide karo (yeh characteristic equation hai): $x^{2} = x + 1 ⟹ x^{2} - x - 1 = 0.$ Positive root hai $x = \frac{1 + 5}{2} = φ \approx 1.618$ — woh golden ratio jo humne upar dekha. Toh call count $φ^{n}$ ki tarah badhta hai, runtime $Θ (φ^{n})$ deta hai. Kyunki $1.618 < 2$ , yeh $2^{n}$ se chota hai lekin kisi bhi polynomial se kaafi bada.

Naive Fibonacci

Θ (φ^{n})

kyun hai aur

Θ (2^{n})

kyun nahi?

Kyunki call tree lopsided hai — ek child fib(n-1) hai, doosra sirf fib(n-2) — toh leaves har level par

φ \approx 1.618

se multiply hote hain,

2

se nahi. Characteristic equation

x^{2} = x + 1

growth base ko golden ratio

φ

par pin karta hai.

Error dhundho

def factorial(n):
    return n * factorial(n - 1)

Yeh galat kyun hai?

Koi base case nahi hai. Yeh forever recurse karta hai (zero se neeche bhi), RecursionError: maximum recursion depth exceeded trigger karta hai. Har recursion ko ek floor chahiye.

def factorial(n):
    if n == 0:
        return 1
    return factorial(n - 1)      # "n *" bhool gaye

Yeh kisi bhi

n

ke liye kya return karta hai, aur kyun?

Hamesha 1. Yeh base tak recurse karta hai aur 1 return karta hai bina kabhi n se multiply kiye — recursive case ka "combine" step missing hai, toh koi actual product nahi banta.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 1)   # dono terms n-1

Yeh galat kyun hai?

Recurrence

F_{n - 1} + F_{n - 2}

honi chahiye,

F_{n - 1} + F_{n - 1}

nahi. Yeh Fibonacci ki jagah

2^{n - 1}

compute karta hai — recursion ki sahi shape, galat subproblem.

def binary_search(arr, target, lo=0, hi=None):
    if hi is None: hi = len(arr)      # len(arr) - 1 hona chahiye
    ...
    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)

Full control flow trace karo: jab target har element se bada ho toh actually kya galat hota hai?

hi = len(arr) ke saath range mein invalid index len(arr) shamil hai. Jaise jaise search right jaati hai, mid len(arr) ki taraf badhta hai; jis moment mid == len(arr), arr[mid] end se aage read karta hai → IndexError. (Agar target present hai, toh yeh pehle luck se sahi index return kar sakta hai — bug sirf right-edge path par bites karta hai, aur yehi wajah hai ki off-by-one range bugs itne sneaky hote hain.)

def binary_search(arr, target, lo, hi):
    mid = (lo + hi) // 2
    if arr[mid] < target:
        return binary_search(arr, target, mid, hi)   # mid, mid+1 nahi
    ...

Yeh forever loop kyun kar sakta hai?

Jab lo aur hi adjacent hain, mid == lo, aur lo = mid (not mid + 1) ke saath recurse karna range ko kabhi nahi shrinkta. Problem ko har call mein strictly chota hona chahiye.

def fib(n, memo={}):
    memo[n] = fib(n-1) + fib(n-2)    # base case check missing
    return memo[n]

Memoization is version ko kyun nahi bachata?

Base case check gone hai, toh yeh zero se neeche forever recurse karta hai kisi bhi cache entry ke help karne se pehle. Memoization ek correct recursion ko speed deta hai; yeh missing base case ko rescue nahi kar sakta.

Mutable default argument def fib(n, memo={}) use karna — isme kaunsa subtle trap hai?

{} ek baar create hota hai aur saari calls mein share hota hai, yahan tak ki alag top-level invocations mein bhi. Cached values persist rehti hain (yahan usually theek hai, lekin surprising) — ek classic Python gotcha jaanna layak hai.

Binary search intervals — window ko shrink hote dekho

Kyun wale questions

factorial(n) mein multiplication recursive call return hone ke baad kyun hoti hai, pehle nahi?

Kyunki n * factorial(n-1) ko pehle factorial(n-1) se ek value milni chahiye. Har pending multiply call stack par baithta hai aur tabhi fire hota hai jab stack base se unwind hota hai.

Memoization

Θ (φ^{n})

Θ (n)

mein kyun badal deta hai?

k = 0 \dots n

ke liye har alag

F_{k}

exactly ek baar compute hota hai aur store hota hai; baad mein requests

O (1)

lookups hain. Kaam unique subproblems ki sankhya ke proportional ho jaata hai, jo

n

hai. Dekho Memoization and Dynamic Programming.

Binary search ko list sorted kyun chahiye, precisely?

Sorted order hi woh cheez hai jo "mid ke left mein sab chota hai, right mein sab bada" ko true banati hai — woh single fact hi hai jo ek comparison ko safely ek poori half discard karne deta hai. Sortedness hatao aur jo half tum throw karte ho usme target ho sakta hai.

Binary search ek Divide and Conquer algorithm kyun hai lekin factorial nahi?

Divide and conquer problem ko parts mein split karta hai aur unhe combine karta hai; binary search search space ko half karta hai. Factorial sirf ek se reduce karta hai har step (linear chain), toh yeh plain recursion hai, divide-and-conquer nahi.

Recurrence

T (n) = T (n /2) + c

ka solution

Θ (lo g_{2} n)

kyun hai?

Pehle iska base case fix karo: size

1

ki problem ek constant amount of work leti hai,

T (1) = c

(ek comparison, aage koi recursion nahi). Ab unroll karo:

T (n) = c + T (n /2) = c + c + T (n /4) = \dots = k \cdot c + T (n / 2^{k})

. Recursion tab rukti hai jab size

1

hit hoti hai, yaani

n / 2^{k} = 1 \Rightarrow k = lo g_{2} n

, aur wahan

T (1) = c

. Toh total work

\approx (lo g_{2} n + 1) c = Θ (lo g_{2} n)

— tum

n

ko utni baar hi half kar sakte ho.

Excessive recursion depth ek correct recursion ko bhi crash kyun kar sakta hai?

Har pending call ek stack frame rakhta hai, aur call stack ki ek finite limit hoti hai (Python ka default ~

1000

hai). Deep-but-valid recursion (jaise factorial(5000)) ise overflow karta hai → RecursionError.

Edge cases

Correct factorial(0) kya return karta hai, aur yeh "kuch nahi" kyun nahi hai?

Yeh 1 return karta hai. Ek empty product

1

define hota hai — pattern

0! = 1! /1 = 1

se forced (opening figure dekho) — aur yeh base ka bhi kaam karta hai jo recursion rok deta hai.

fib(0) aur fib(1) kya return karte hain, aur dono ko hard-code kyun karna padta hai?

Respectively 0 aur 1. Yeh do seeds hain jahan tak recurrence peeche jaati hai; dono ke bina, fib(1) nonexistent fib(-1) use karne ki koshish karega.

Empty list [] par binary search — kya hota hai?

hi = len(arr) - 1 = -1, toh lo (

0

)

>

hi (

- 1

) immediately true hai →

- 1

return karta hai (not found). Empty-range base case ise cleanly handle karta hai.

Binary search ek target ke liye jo har element se chota hai — shrink trace karo.

Har comparison arr[mid] > target pata hai, toh hi tab tak left jaata rehta hai jab tak lo > hi →

- 1

return. Yeh kabhi spin nahi karta; range strictly empty hoti jaati hai.

Single-element list [5] par binary search 5 ke liye vs 3.

5 ke liye: lo=hi=0, mid=0, arr[0]==5 → 0 return. 3 ke liye: arr[0]=5>3 → hi=-1, phir lo>hi →

- 1

return. Dono ek ya do steps mein terminate karte hain.

Standard if n == 0 base ke saath factorial(-1) — safe hai ya nahi?

Safe nahi. Yeh kabhi n == 0 nahi hit karta,

- 1, - 2, - 3, \dots

forever recurse karta hai → RecursionError. Negative inputs definition ke bahar hain aur upfront reject hone chahiye.

Binary search ke liye, agar list mein duplicate targets hain — result deterministic hai?

Haan, ek fixed list ke liye deterministic: same mid sequence har baar chalti hai, same index return karti hai. Lekin yeh guaranteed nahi ki pehla ya aakhri duplicate ho — sirf ek valid wala.

Woh sabse chota

n

kya hai jahan naive fib(n) noticeably lag karta hai, aur yeh itna suddenly kyun aata hai?

fib(35)–fib(40) ke aaspaas. Kyunki cost

φ^{n}

ki tarah badhti hai, har extra

n

kaam ko

\approx 1.6

se multiply karta hai — slowdown bilkul sudden lagti hai kyunki exponential growth sasta rehta hai phir blast ho jaata hai.

Recall Ek-line self-test

Upar ke answers cover karo. Kya tum, har ek chaar failure modes ke liye — missing base case, wrong subproblem, off-by-one range, unsorted input — woh exact symptom bata sakte ho jo woh produce karta hai (infinite recursion / RecursionError, ek galat value, ek IndexError ya endless loop, aur unreliable results)? Agar tum bina dekhay har failure ko uske symptom ke saath pair kar sakte ho, toh yeh topic tumhara hai.

Connections

Recursion vs Iteration — yahan har trap ka ek loop-based analogue hai
Big-O Notation — $φ^{n}$ vs $lo g n$ reasoning aur $Θ$ notation
Memoization and Dynamic Programming — repeated subproblems ka fix
Divide and Conquer — binary search kyun half karta hai aur factorial nahi
The Call Stack and Stack Frames — RecursionError ka source
Sorting Algorithms — woh precondition jo binary search silently assume karta hai