Exercises — Classic recursion — factorial, Fibonacci, binary search

Base case: if n == 0: … return. Kyun: yahi ek aise branch hai jo countdown ko dobara call kiye bina return karta hai. Ye tab reach hota hai jab input shrink hote hote $0$ tak aa jaata hai. Iske bina, countdown(n-1) $-1,-2,\dots$ tak jaata rehta → RecursionError.

$s(n)=n+s(n-1),s(0)=0.$ $n+s(n-1)$ kyun? $n$ tak ka total hai "$n$ khud" ko "$n-1$ tak ke total" ke saath jodna — yahi self-similar structure hai. $s(0)=0$ kyun? Koi bhi number na jodhne par $0$ milta hai (empty sum), aur ye chain ko rok deta hai.

Do base cases: $F_0=0$ aur $F_1=1$. Do kyun? Recurrence $F_n=F_{n-1}+F_{n-2}$ do steps peeche jaati hai. Agar sirf $F_0$ anchor karo, toh $F_1$ compute karne par $F_{-1}$ maanga jaayega — floor ke neeche — aur ruk hi nahi payega. Jitne steps recurrence peeche jaaye, utne hi fixed starting values chahiye.

factorial(4) = 4 * factorial(3)
             = 4 * (3 * factorial(2))
             = 4 * (3 * (2 * factorial(1)))
             = 4 * (3 * (2 * (1 * factorial(0))))
             = 4 * (3 * (2 * (1 * 1)))     # base case 0! = 1
             = 24

Ye order kyun? Har multiplication call stack par wait karti hai jab tak base case factorial(0)=1 return nahi karta, phir products bottom-up resolve hote hain: $1,1,2,6,24$. Answer: $24$.

Indices: 2→0, 4→1, 6→2, 8→3, 10→4, 11→5, 14→6. Start karo lo=0, hi=6 se.

mid = (0+6)//2 = 3; kyunki $8<11$ hai, poora left half (indices 0–3) phenk diya jaata hai. Agle mein mid = (4+6)//2 = 5, aur arr[5]==11. Answer: index $5$ return hota hai.

Recurrence: $b^n=b\times b^{n-1}$ ($b$ ka ek factor alag karo), base: $b^0=1$ (empty product).

def power(b, n):
    if n == 0:            # base case: b^0 = 1
        return 1
    return b * power(b, n - 1)   # recursive case

Trace: $2^5=2\cdot 2^4=2\cdot 2\cdot 2^3=\cdots =2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 1=32$. Answer: $32$.

Frames factorial(100), factorial(99), …, factorial(0) ke liye exist karte hain — yani $100$ se $0$ tak har integer ke liye inclusive: $100-0+1=101$ frames. General formula: factorial(n) depth $n+1$ tak jaati hai. 100 ke liye answer: $101$ frames. Yahi wajah hai ki bahut bade $n$ par RecursionError aa sakta hai — Python ka default recursion limit lagbhag $1000$ frames ka hai.

Counter ki recurrence: fib(n) khud ke liye ek call, plus uske do children ki saari calls: $C(n)=1+C(n-1)+C(n-2).$ Build up karte hain: $C(2)=1+C(1)+C(0)=1+1+1=3$ $C(3)=1+C(2)+C(1)=1+3+1=5$ $C(4)=1+C(3)+C(2)=1+5+3=9$ $C(5)=1+C(4)+C(3)=1+9+5=15$ Answer: $15$ calls. (Ghaur karo ki $15$ zyada hai $6$ distinct values $F_0\dots F_5$ se — baaki $9$ redundant recomputations hain. Dekho Big-O Notation.)

Har comparison remaining range ko half kar deta hai, isliye worst case woh halvings ki sankhya hai jo $1000$ ko $1$ tak shrink karne mein lagti hain: $\lfloor {\log }_{2}1000\rfloor +1=9+1=10.$ Check: $2^9=512<1000\le 1024=2^{10}$, toh zyada se zyada $10$ baar half kar sakte hain. Answer: $10$ comparisons. Linear search ke worst case $1000$ se compare karo — yahi $\Theta (\log n)$ ka fayda hai.

Idea: list ka sum hai "uska pehla element" plus "baaki ka sum".

def sum_list(a):
    if len(a) == 0:        # base case: empty list ka sum 0 hai
        return 0
    return a[0] + sum_list(a[1:])   # pehla + baaki ka sum

Recurrence: $S(a)=a_0+S(a_{1:})$, base $S([])=0$. Trace: $4+(2+(7+(1+0)))=4+2+7+1=14$. Answer: $14$.

Idea: pehle character ko end mein le jao, baaki ko reverse karne ke baad.

def reverse(s):
    if len(s) <= 1:        # base case: empty ya single char khud ka reverse hai
        return s
    return reverse(s[1:]) + s[0]   # tail reverse karo, phir head append karo

Trace:

reverse("cat") = reverse("at") + "c"
               = (reverse("t") + "a") + "c"
               = ("t" + "a") + "c"       # base: "t" reverse hokar "t" hi
               = "tac"

Answer: "tac".

def gcd(a, b):
    if b == 0:          # base case: gcd(a,0)=a
        return a
    return gcd(b, a % b)   # chhoti problem: remainder tezi se shrink hota hai

Trace:

gcd(48,18) = gcd(18, 48%18) = gcd(18, 12)
           = gcd(12, 18%12) = gcd(12, 6)
           = gcd(6,  12%6)  = gcd(6, 0)
           = 6              # base case

Ye rukta kyun hai? Remainder $a\mathrm{mod}b$ hamesha $b$ se strictly chhota hota hai, isliye b har call mein ghatta hai aur zaroori $0$ tak pahunchega. Answer: $6$.

Python mein, ek default argument ek baar create hota hai — jab function define hota hai — har call par nahi. Isliye wahi memo dict un sabhi calls mein share hoti hai jo apni khud ki pass nahi karti.

• Khatara: fib(50) ki cache fib(30) mein bachi rehti hai. Yahan ye harmless hai (cached Fibonacci values sahi hain aur speed bhi badhti hai), lekin yahi pattern ek list default ke saath (jaise def add(x, box=[])) calls ke beech results leak karwata hai — ek classic bug.
• Safe fix: memo=None use karo aur andar if memo is None: memo = {} set karo, jisse har top-level call ko fresh cache mile jabki recursion mein neeche share hoti rahe. Key insight: memoized fib ki correctness yahan shared dict ke saath sirf isliye bachi rehti hai kyunki Fibonacci values kabhi badlti nahi; generally is luck par rely mat karo.

Idea (ek Divide and Conquer move): agar $n$ even hai, toh $b^n=(b^{n/2}{)}^2$ — half-power ek baar compute karo, phir square karo. Agar $n$ odd hai, toh $b^n=b\cdot b^{n-1}$.

def fast_power(b, n):
    if n == 0:
        return 1
    half = fast_power(b, n // 2)
    if n % 2 == 0:
        return half * half
    return b * half * half

Trace $3^{10}$:

3^10 = (3^5)^2
3^5  = 3 * (3^2)^2
3^2  = (3^1)^2
3^1  = 3 * (3^0)^2 = 3*1*1 = 3

Toh $3^2=9$, $3^5=3\cdot 9\cdot 9=243$, $3^{10}=243^2=59049$. Recurrence: $T(n)=T(n/2)+O(1)\Rightarrow \Theta (\log n)$ — binary search jaise hi shape. Answer: $3^{10}=59049$.

Start karo lo=0, hi=4 se. mid = (0+4)//2 = 2, arr[2] = 5. Kyunki $5<7$, code assume karta hai ki index 2 ke baaye sab chhota hai aur use phenk deta hai, right mein lo=3 ke saath search karta hai.

call 1: lo=0 hi=4 mid=2 arr[mid]=5  -> 5<7 -> go right lo=3
call 2: lo=3 hi=4 mid=3 arr[mid]=3  -> 3<7 -> go right lo=4
call 3: lo=4 hi=4 mid=4 arr[mid]=7  -> found, return 4

Yahan ittefaaq se mila — lekin ye sirf kismet hai. Agar target = 1 hota (index 1 par), toh pehला step $5>1$ use left mein indices 0–1 ki taraf bhej deta, jahan arr hai [9,1], aur comparisons ke hisaab se galat index ya -1 return ho sakta tha. Kyun toot jaata hai: halving logic depend karta hai "mid ke baaye ≤ mid ≤ mid ke daaye" par, jo exactly sorted property hai. Ye guarantee hatao aur aadhe ko eliminate karna bejaa ho jaata hai. Fix: pehle sort karo ($\Theta (n\log n)$, dekho Sorting Algorithms) ya linear search use karo.

L2.1 24 · L2.2 5 · L2.3 32 · L3.1 101 · L3.2 15 · L3.3 10 · L4.1 14 · L4.2 "tac" · L4.3 6 · L5.2 59049