Noesis
1.2.37 · D1 · HinglishIntroduction to Programming (Python)

Foundations — Recursion — call stack visualization, base case, recursive case

1,930 words9 min read↑ Read in English

1.2.37 · D1 · Coding › Introduction to Programming (Python) › Recursion — call stack visualization, base case, recursive c

Parent note padhne se pehle, tumhe us mein aane waale har notation piece ko poori tarah samajhna hoga. Yeh page bilkul zero se shuru hota hai aur har symbol ko ek-ek karke build karta hai. Koi bhi cheez use hone se pehle properly explain ki jaati hai.

1. Function kya hota hai? (woh box jo khaata aur return karta hai)

Figure dekho: input left side se jaata hai, machinery kaam karti hai, aur exactly ek value right side se baahir aati hai (woh return value hai).

Figure — Recursion — call stack visualization, base case, recursive case

Python mein yeh box aise likha jaata hai:

def double(x):      # 'def' = "define a box named double that eats x"
    return x + x    # hand back x + x, then stop
  • def ::: woh keyword jo box definition shuru karta hai.
  • double ::: box ka naam — jisse tum baad mein call karte ho.
  • (x) ::: parameter, jo bhi input pass karo uske liye ek placeholder.
  • return x + x ::: x + x compute karo, phir use baahir bhejo aur ruk jao.

Inputs aur outputs ki poori kahani ke liye Functions and return values dekho.

2. Function ko call karna (aur khud ko call karna)

Ek function khud ko bhi alag input ke saath call karne ki permission rakhta hai:

def f(n):
    return f(n - 1)   # f calls f — this is recursion (careful: no stop here!)

Woh line — ek box apna naam khud ke andar use karna — recursion ka seed hai. Yeh tabhi safe banta hai jab hum ek stopping rule add kar lete hain (Section 6).

3. Symbol n aur operation n - 1

Figure mein number line dekho: har recursive call marker ko ek jagah left slide karta hai, special stopping value ki taraf badhta hua.

Figure — Recursion — call stack visualization, base case, recursive case

4. Lists aur slice L[0], L[1:]

Parent ka doosra example lists use karta hai, isliye hum unhe zero se define karte hain.

Colon : ka matlab hai "aur jo baad mein aata hai sab." Figure list ko head (L[0], ek item) aur tail (L[1:], bacha hua) mein split hote dikhata hai.

Figure — Recursion — call stack visualization, base case, recursive case

5. Factorial symbol n!

Parent ki main derivation n! use karti hai, toh chalte hain yeh symbol samajhte hain.

6. Base case vs recursive case (do zaroori hisse)

Ab poore topic ke do starring terms.

Figure woh fork dikhata hai jo har recursive function mein hota hai: upar ek sawaal ("kya input chhota hai?"), ek ruko-aur-jawab-do branch (base case), aur ek chhoto-aur-dobara-call-karo branch (recursive case).

Figure — Recursion — call stack visualization, base case, recursive case

7. Call stack: LIFO, frames, RecursionError

Memory-level picture ke liye The Call Stack and Stack Frames dekho, aur kitna deep zyada hai uske liye Big-O and Recursion Depth dekho.

Prerequisite map

Function - box that eats input

return - hand a value back

Call - run with an input

Call itself - recursion seed

n minus 1 - shrink by one

Recursive case

List slice L1 onward - the rest

Factorial n bang - self similar product

Base case - known answer stops it

Call stack - pile of frames LIFO

Recursion - the topic

Har foundation agli ko feed karta hai: ek function jo return aur call itself kar sake, plus input ko chhota karne ka tarika (n-1, L[1:]), plus ek known stopping value (base case), sab call stack ke zariye manage hota hua.

Equipment checklist

Khud test karo — right side chhupaao aur reveal karne se pehle answer karo.

return ek function ke andar kya karta hai?
Caller ko ek value wapas bhejta hai aur turant us function ko rok deta hai.
Agar ek function mein return nahi hai, toh kya value baahir aati hai?
None (woh empty "kuch nahi" value).
"Call" kya hota hai?
Ek function ko specific input ke saath actually run karna.
n - 1 recursive call mein kya guarantee karta hai?
Input ek step chhota hota hai, isliye recursion apne stopping point ki taraf badhti hai.
List [4, 2, 7] ke liye L[0] kya hai aur L[1:] kya hai?
L[0] hai 4 (head); L[1:] hai [2, 7] (rest/tail).
n! ka kya matlab hai, aur 0! kya hota hai?
Product 1·2·3···n; aur 0! ki definition 1 hai.
Factorial ke liye self-similar rule batao.
n! = n · (n-1)!.
Base case kya hota hai?
Sabse chhota input jiska answer seedha pata hai, bina aage recursive call kiye — yeh recursion ko rokta hai.
Recursive case kya hota hai?
Woh branch jo function ko chhote input par call karta hai aur us result ko combine karta hai.
Stack frame kya hota hai, aur kya do calls n share karte hain?
Ek call ke liye ek private notepad jo apne locals rakhta hai; nahi, har call ka apna alag independent n hota hai.
Call stack ke liye LIFO ka kya matlab hai?
Last In, First Out — sabse aakhir mein push hua (sabse deep) frame pehle khatam hoke pop hota hai.
Jab koi working base case nahi hota toh kaun sa error aata hai?
RecursionError: maximum recursion depth exceeded.

Ready ho? Parent par wapas jao: main note fact build karta hai aur stack ko exactly inhi pieces use karke trace karta hai. Loops prefer karte ho? Iteration — for and while loops se compare karo.