Classic recursion — factorial, Fibonacci, binary search

1.2.38 · Coding › Introduction to Programming (Python)

The two parts every recursion MUST have

1. Factorial

Scratch se recurrence derive karo. WHAT hai $n!$ ? Yeh hai $n$ times uske neeche sab cheez ka product: $n! = n \times = (n - 1)! (n - 1) (n - 2) \dots 1 = n \cdot (n - 1)!$ To $n! = n \cdot (n - 1)!$ — yahi hai recursive case. WHY base case $0! = 1$ ? Ek empty product $1$ hota hai (kuch se multiply karna kuch nahi badalta), aur yeh chain ko rokta hai.

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

Worked example

factorial(3) trace karna — Har step WHY?

factorial(3) = 3 * factorial(2)      # Why? n! = n*(n-1)!
            = 3 * (2 * factorial(1)) # Why? same rule, smaller n
            = 3 * (2 * (1 * factorial(0)))
            = 3 * (2 * (1 * 1))      # Why? base case 0! = 1
            = 6

Why this order? Multiplications stack par wait karti hain jab tak base case return nahi karta, phir bottom-up unwind hoti hain.

2. Fibonacci

WHY do base cases? Recurrence do steps peeche jaati hai, to tumhe do known starting values chahiye, warna tum $F_{0}$ se bhi neeche recurse kar lete.

def fib(n):
    if n < 2:                 # base cases: F0=0, F1=1
        return n
    return fib(n - 1) + fib(n - 2)

Common mistake Steel-man: "Naive Fibonacci theek hai, yeh sirf recursion hai."

Why it feels right: yeh math definition ko perfectly mirror karta hai aur sahi answers deta hai. The trap: yeh same subproblems ko exponentially recompute karta hai. fib(5) fib(3) ko do baar call karta hai, fib(2) ko teen baar… Runtime hai $\approx Θ (φ^{n})$ jahaan $φ \approx 1.618$ . fib(40) already crawl karta hai. The fix: memoize karo — jo answers tum dekh chuke ho unhe cache karo.

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]

Ab har $F_{k}$ ek baar compute hota hai → $Θ (n)$ .

Worked example WHY naive

fib slow hai — call tree

           fib(4)
         /        \
     fib(3)      fib(2)     <- fib(2) computed AGAIN below too
     /    \       /   \
  fib(2) fib(1) fib(1) fib(0)

Why repeated? fib(2) do alag branches mein appear karta hai; koi memory nahi matlab redundant kaam.

Figure — Classic recursion — factorial, Fibonacci, binary search

3. Binary Search (recursive)

Time bound derive karo. Agar $T (n)$ $n$ elements ke liye kaam hai: $T (n) = T (n /2) + c$ (ek comparison, phir half problem). Unrolling: $T (n) = c \cdot (lo g_{2} n) + T (1) = Θ (lo g_{2} n)$ .

def binary_search(arr, target, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo > hi:                  # base case: empty range -> not found
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == target:       # base case: found it
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)   # search right half
    else:
        return binary_search(arr, target, lo, mid - 1)   # search left half

Worked example

[1,3,5,7,9,11] mein target=7 search karo

call	lo	hi	mid	arr[mid]	decision (Why?)
1	0	5	2	5	$5 < 7$ → right jao, `lo=3`
2	3	5	4	9	$9 > 7$ → left jao, `hi=3`
3	3	3	3	7	mila → return `3`
Why halving each time? Sorted order guarantee karta hai ki `mid` ke left mein sab chota hai, right mein sab bada — to ek comparison se pura ek half safely eliminate ho jaata hai.

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho tumhe ek giant dictionary mein ek word dhundhna hai. Tum beech mein kholte ho: agar tumhara word pehle aata hai, to doosra half faad do aur sirf pehle mein dekho; agar baad mein, to pehla half faad do. Baar baar half karte raho — tum ise bahut fast dhundh lete ho. Yahi hai binary search. Recursion ek line of people jaisi hai jo ek question peeche pass karte hain: "Mujhe $5!$ nahi pata, lekin agar peeche waala mujhe $4!$ bataye, to main bas 5 se multiply kar dunga." Har insaan agla poochta hai, jab tak aakhiri insaan easy answer nahi jaanta ( $0! = 1$ ) aur usse aage pass karta hai. Fibonacci hai "agla number = pichle do ka sum," lekin agar tum bina answers likhe wahi choti choti questions baar baar poochte raho, to bahut time waste hoga — to unhe note karo (memoize karo)!

Flashcards

Har recursive function mein kaunse do parts hone chahiye?

Ek base case (recursion rokta hai) aur ek recursive case (khud ko chote input par call karta hai).

Factorial ke liye

0! = 1

base case kyun hai?

Ek empty product 1 ke barabar hota hai, aur yeh recursive chain ko rokta hai.

Factorial ke liye recurrence?

n! = n \cdot (n - 1)!

, with

0! = 1

Fibonacci ko do base cases kyun chahiye?

Recurrence do steps peeche jaati hai (

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

), to do starting values zaroori hain.

Naive recursive Fibonacci ki time complexity kya hai aur kyun?

Θ (φ^{n})

exponential — yeh same subproblems ko kai baar recompute karta hai.

Recursive Fibonacci ko fast kaise banate ho?

Memoize (cache) karo computed values ko →

Θ (n)

Binary search ke liye precondition kya hai?

Array sorted hona chahiye.

Binary search

Θ (lo g n)

kyun hai?

Har step search space ko half karta hai:

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

Binary search ke base cases?

lo > hi (range empty → not found) aur arr[mid]==target (found).

Python mein missing/unreachable base case kaunsa error cause karta hai?

RecursionError: maximum recursion depth exceeded (stack overflow).

Machine pending recursive calls yaad rakhne ke liye kaunsa data structure use karti hai?

The call stack (stack frames).

Connections

Recursion vs Iteration — har recursion ko ek loop + stack se rewrite kiya ja sakta hai
Big-O Notation — aise humne $Θ (n)$ , $Θ (lo g n)$ , $Θ (φ^{n})$ derive kiya
Memoization and Dynamic Programming — subproblem answers ko cache karna
Divide and Conquer — binary search iska sabse simple example hai
The Call Stack and Stack Frames
Sorting Algorithms — binary search ke liye prerequisite