Foundations — Classic recursion — factorial, Fibonacci, binary search

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

Is page par assume kiya gaya hai ki aap kuch nahi jaante. Parent page ka har symbol neeche unpack kiya gaya hai, ek aisi order mein jahan har idea sirf usse pehle wale ideas pe lean karta hai.

0. Woh picture jis par sab kuch tika hai

Kisi bhi symbol se pehle, dekho ki recursion kya karta hai.

1. Ek variable aur symbol =

Picture: ek box jiski name-tag n hai aur andar 3 baitha hai.

Topic ko kyun chahiye: har recursive function mein ek input box hota hai (usually n, lo, hi, ya target naame). Trace follow karne ke liye yeh jaanna zaroori hai ki ek naam sirf us waqt jo bhi box mein hai, usi ki taraf point karta hai.

2. Symbol n aur "chhota" ka matlab

Picture: §0 mein tall box ki height. "Chhota subproblem" simply matlab hai ek chhota box — $n-1$, ya $n/2$, ya list ka ek chhota slice.

Topic ko kyun chahiye: recursion tabhi terminate hoti hai jab har call strictly chhoti hoti hai. Agar box kabhi nahi shrink karta, toh aap chhote base box tak kabhi nahi pahunchte, aur pile forever badhti rehti hai.

3. Chaar arithmetic symbols +, -, * (×), /

Parent page par har formula sirf chaar operations se bana hai. Yeh rahe, zero se.

Topic ko kyun chahiye: n - 1 (subtract) se factorial aur binary search problem ko chhota banate hain; F_{n-1} + F_{n-2} (add) poora Fibonacci rule hai — do chhote answers ko jodte hain.

Parent factorial ko multiplications ki chain ki tarah likhta hai: $n!=n\times (n-1)\times \cdots \times 2\times 1$

Topic ko kyun chahiye: factorial ek product hai, aur iska base case $0!=1$ empty product hai. Is idea ke bina base case arbitrary lagta hai.

4. Factorial symbol !

Picture: blocks $3,2,1$ ka ek staircase jo saath multiply hote hain.

5. Subscripts aur Fibonacci symbols $F_n$

Picture: boxes ki ek row $F_0,F_1,F_2,\dots$ label ki hui, har ek mein ek Fibonacci number rakha hai.

Topic ko kyun chahiye: kyunki rule do boxes peeche jaata hai, aapko do known starting boxes chahiye ($F_0,F_1$) — yahi exactly "two base cases" hai jis par parent zor deta hai.

6. Lists, indices, aur [ ] notation

7. Floor division // — kyun hamen / ke saath iska bhi zaroorat hai

Topic ko kyun chahiye: binary search hamesha middle slot par jump karta hai, aur slots whole numbers hote hain — toh yeh / nahi, // use karta hai.

8. Comparisons: ==, <, >

Picture: ek balance scale. arr[mid] < target baayin taraf jhukta hai → value bahut chhoti hai → answer sorted list mein aur daayein hona chahiye.

Topic ko kyun chahiye: har base case ek comparison hai — if n == 0, if lo > hi, if arr[mid] == target. Har ek ek sawaal hai jo decide karta hai "ruko, ya chhote mein recurse karo."

9. Functions aur words def, return, "call"

Picture: ek vending machine. Aap inputs daalo (3), go dabao (call), aur ek value bahar aati hai (return). Ek recursive call matlab machine apna khud ka button ek chhote input ke saath dabati hai.

Topic ko kyun chahiye: recursion literally matlab hai "ek function jo khud ko call karta hai." return ke bina, chhota answer kabhi §0 ki chain mein upar wapas nahi jaata.

10. Call stack — jahan "pile up then unwind" rehta hai

Topic ko kyun chahiye: yeh explain karta hai ki factorial mein multiplications kyun wait karti hain, phir bottom-up combine hoti hain — stack topic ki hidden memory hai.

11. Growth symbols: $\Theta$, ${\log }_{2}n$, aur $\phi$

Picture: ${\log }_{2}n$ ek dheere badhne wala curve hai (halving fast hai); ${\phi }^n$ ek rocket hai (repeated multiplication). Same axis, wildly alag climbs.

Topic ko kyun chahiye: yahi teen symbols hain jisse parent ka summary table factorial ($\Theta (n)$), binary search ($\Theta (\log n)$), aur naive Fibonacci ($\Theta ({\phi }^n)$) compare karta hai.

12. Recurrence notation $T(n)$

Topic ko kyun chahiye: in recurrences ko unroll karna hi woh tarika hai jisse parent $\Theta (n)$ aur $\Theta (\log n)$ derive karta hai. $T$ recursion hai jo apni khud ki cost recursively describe kar raha hai — bilkul fitting.

Prerequisite map

Neeche diagram ek flowchart hai: har rounded label is page ka ek idea hai, aur ek arrow → matlab hai "arrow ki tail wala idea, head wale idea se pehle chahiye." Arrows ko "feeds into" ki tarah padhiye. Koi bhi path upar se neeche follow karo aur aap safe learning order mein chal rahe ho: basic symbols left/top par, teen recursion problems beech mein, cost language neeche.

Equipment checklist

Khud test karo — right side cover karo aur har ek ka jawaab do.

Connections

• Classic recursion — factorial, Fibonacci, binary search — woh parent jiske liye yeh page aapko taiyaar karta hai
• The Call Stack and Stack Frames — §10 poori detail mein
• Big-O Notation — §11 ki $\Theta$, $\log$, $\phi$ growth language
• Recursion vs Iteration — jab aap stack jaano, loops ek alternative hain
• Memoization and Dynamic Programming — ${\phi }^n$ blow-up ka ilaaj
• Divide and Conquer — binary search ke peeche "aadha karo" wala idea
• Sorting Algorithms — kyun binary search ko sorted list chahiye