1.2.37
Recursion tab hoti hai jab ek function khud ko call karta hai usi problem ke ek chote version ko solve karne ke liye, jab tak problem itni choti na ho jaye ki seedha answer diya ja sake.
Yeh kaam kyun karta hai? Kyunki bahut saari problems self-similar hoti hain: ek badi problem ka answer ek thodi choti problem ke answer se banta hai. Agar aap lagataar chhotaa karte raho, toh aap eventually ek aisi case pe pahunch jaate ho jo aap pehle se jaante ho — aur phir aap wapas upar build karte ho.
Soch lo nested Russian dolls: "saari dolls process karne" ke liye, ek kholo, phir baaki ko exactly usi tarah process karo, jab tak sabse choti solid doll na aa jaye (base case).
Ek recursive function woh function hota hai jo apne aap ke terms mein define hota hai. Iske do mandatory parts hote hain:
Base case bina recursion ke pata ho. Yeh recursion ko rok deta hai.Recursive case chote/simple input pe call karta hai, phir us result ko combine karta hai.
Sahi base case nahi hoga → infinite recursion → RecursionError (stack overflow).
Intuition DONO parts kyun chahiye
Recursive case progress karta hai (problem ko chhotaa karta hai).Base case guarantee karta hai ki yeh chhota hona eventually khatam hoga.
Ek seedhi: har recursive call ek stair neeche jaati hai; base case zameen hai. Zameen nahi toh hamesha girte rahoge.
Call stack memory ka woh region hai jo har active (abhi-tak-khatam-na-hui) function call ke liye ek stack frame store karta hai. Har frame us call ki local variables aur "kahan return karna hai" yeh rakhta hai. Yeh ek LIFO (Last-In-First-Out) structure hai: jo function sabse baad call hua woh pehle khatam hota hai.
Intuition Har recursion ke do phases
Winding (descent): har call ek naya frame push karti hai aur pause ho jaati hai, apni sub-call ka intezaar karti hai. Frames pile hote jaate hain.Unwinding (return): base case ek value return karta hai; har paused frame resume hoti hai, apna result compute karti hai, return karti hai, aur pop ho jaati hai.
Hum chahte hain n ! = 1 ⋅ 2 ⋅ 3 ⋯ n
Step 1 — Self-similarity dhundho.
Notice karo n ! = n ⋅ ( n − 1 )! Yeh step kyun? Kyunki 1.. n n 1.. ( n − 1 ) hai recursive case.
Step 2 — Dhundho kahan chhota hona ruk jaata hai.
( n − 1 )! ( n − 2 )! 0 ! 0 ! = 1 Yeh step kyun? Humein ek aisa input chahiye jiska jawab aur recursion ke bina de sakein. 0 ! = 1
Step 3 — Function mein combine karo.
def fact (n): if n == 0 : # base case return 1 return n * fact(n - 1 ) # recursive case
fact(3) trace karo — stack dekho
Winding (frames push karo):
fact(3) → chahiye 3 * fact(2) → pause , push fact(2)fact(2) → chahiye 2 * fact(1) → pause , push fact(1)fact(1) → chahiye 1 * fact(0) → pause , push fact(0)fact(0) → base case → returns 1 (aur koi call nahi)
Unwinding (frames pop karo, upar aate waqt multiply karo):
fact(1) resume: 1 ⋅ 1 = 1 fact(2) resume: 2 ⋅ 1 = 2 fact(3) resume: 3 ⋅ 2 = 6
Yeh order kyun? Sabse gehra call (base case) pehle khatam hota hai (LIFO), toh multiplications wapas upar aate waqt bahar-se-andar hoti hain.
Worked example Doosra example — list ka sumsumm([4, 2, 7])
Self-similarity: sum ( L ) = L [ 0 ] + sum ( L [ 1 : ]) 0
def summ (L): if not L: # base case: empty list return 0 return L[ 0 ] + summ(L[ 1 :]) # recursive case Trace: summ([4,2,7]) → 4 + summ([2,7]) → 4 + (2 + summ([7])) → 4 + (2 + (7 + summ([]))) → 4 + (2 + (7 + 0)) = 13 .
L[1:] kyun?zaroor [] tak pahunchenge.
Worked example Forecast-then-VerifyForecast: count_down(2) kya print karega
def count_down (n): if n < 0 : return print (n) count_down(n - 1 ) Pehle predict karo phir padho → 2, 1, 0 phir ruk jaata hai.
Verify: n=2→print 2; n=1→print 1; n=0→print 0; n=-1→base case, return. ✅
Call se PEHLE print kyun? Kyunki print winding ke dauran hota hai. Agar aap print(n) ko count_down(n-1) ke baad le jaao, toh woh unwinding ke dauran print karega → 0,1,2.
Common mistake "Mujhe base case ki zaroorat nahi, inputaise bhi chhotaa hota jaata hai."Kyun sahi lagta hai: recursive call clearly n Fix: "chhotaa" tabhi matter karta hai jab koi value explicitly pakdi aur return ki jaaye. if n == 0: return ... ke bina, Python fact(-1), fact(-2), … call karta rehta hai → RecursionError: maximum recursion depth exceeded. Base case hi sirf woh cheez hai jo ise rokti hai.
Common mistake "Recursive case ne problem ko chhotaa karna bhool gaya."return n * fact(n-1) ki jagah return n * fact(n) likhna.
Kyun sahi lagta hai: yeh lagta hai jaise khud ko call kar raha hai, jo "recursion" hai.
Fix: har recursive call ko base case ki taraf move karna chahiye (n-1, L[1:], half karo, etc. use karo). Progress nahi = infinite recursion.
Common mistake "Recursion automatically return karta hai."Recursive case ko fact(n-1) likhna (na return, na multiply).
Kyun sahi lagta hai: tumne function call kiya, toh iska answer wapas aana chahiye.
Fix: inner call ki return value tab tak waste ho jaati hai jab tak tum return nahi karte (ya store/combine nahi karte). Hamesha return n * fact(n-1) likho.
Common mistake "Stack frames share kiye jaate hain."Yeh maanna ki saari calls ek hi n use karti hain.
Kyun sahi lagta hai: har jagah same variable name hai.
Fix: har frame ke apne independent locals hote hain . fact(3) ka n=3 aur fact(2) ka n=2 ek saath stack pe exist karte hain.
Intuition Recursion kab use karoJo bhi self-similar / tree-shaped ho (factorials, Fibonacci, folders traverse karna, nested data parse karna) woh recursion ke saath natural hai. Plain counting loops usually for/while ke saath simple hoti hain. Har recursion ko loop mein rewrite kiya ja sakta hai (Python depth ~1000 tak limit karta hai), lekin recursion aksar math definition ke zyada paas padha jaata hai.
B.A.S.E.
B ase case pehle (stop karne wala) · A lways input chhotaa karo · S ave the return value (use combine karo) · E ach call ka apna frame hota hai.
Recall Feynman: 12 saal ke bachche ko samjhaoSocho tum ek lambi line mein khade ho aur apni position jaanna chahte ho. Tum aage dekh nahi sakte, toh aage waale ko tap karte ho aur poochte ho "tera number kya hai?" Woh same cheez karta hai, agle ko tap karta hai, aur yeh silsila chalta rehta hai — jab tak bilkul pehla insaan kehta hai "main number 1 hoon!" (yeh base case hai — woh bina kisi se pooche jawab deta hai). Phir answer wapas aata hai: har insaan jo suna usme 1 jodta hai aur peeche waale ko bataata hai. Yehi recursion hai: khud ki ek choti copy se poochho, wait karo, phir apna hissa add karo. "Jawab ka intezaar karne waale log" call stack hain.
Har recursive function mein kaunse do parts hone chahiye? Ek base case (recursion rokta hai) aur ek recursive case (khud ko chote input pe call karta hai).
Base case kya hota hai? Sabse chota input jiska answer directly pata ho, bina aur recursive call ke — yeh recursion ko rokta hai.
Missing/wrong base case crash kyun karta hai? Recursion kabhi nahi rukta, frames pile ho jaate hain, aur Python maximum recursion depth hit kar leta hai → RecursionError (stack overflow).
Active function calls kaunsa data structure store karta hai, aur woh kaunsa order follow karta hai? Call stack, jo LIFO (last-in-first-out) hota hai.
fact(3) mein kaunsi call apni value PEHLE return karti hai?fact(0) — base case — kyunki sabse gehra/last-pushed frame pehle khatam hota hai (LIFO).
Ek recursive run ke do phases kaunse hain? Winding (frames push karte hue neeche jaana) aur unwinding (frames pop karte hue aur return combine karte hue wapas aana).
Recursive call mein n-1 (ya L[1:]) kyun use karna chahiye? Base case ki taraf progress karne ke liye; warna problem kabhi nahi chhotaati aur recursion infinite ho jaata hai.
Agar recursive case mein return bhool jaao toh kya hoga? Sub-call ka result discard ho jaata hai; function computed value ki jagah None return karta hai.
Kya saari recursive calls ek hi local variable n share karti hain? Nahi — har stack frame ke apne independent locals ka copy hota hai.
Recursion derive karne ke liye use ki gayi factorial ki self-similar definition? n! = n · (n-1)! jahan 0! = 1.
RecursionError stack overflow
