Theory
वह function जो ख़ुद को phone करता है
अब तक आपने लिखा हर function दूसरे functions को call करता है। आज का twist पहली बार सुनने पर illegal लगता है:
fact(4) अपना answer... fact(3) call करके compute करता है। जो fact(2) को call करता है। जो fact(1) को call करता है।
एक function ख़ुद को call कर रहा है। Students recursion से या तो प्यार करते हैं या डरते हैं, और फ़र्क़ हमेशा एक चीज़ है: क्या उन्होंने इसे एक बार, धीरे-धीरे, हाथ से trace किया है। बिल्कुल यही हम करेंगे।
Theory
Queue के नीचे पूछना
आप canteen line में 8वें हैं और अपनी position जानना चाहते हैं, पर front नहीं देख सकते। तो आप आगे वाले व्यक्ति से पूछते हैं: "आपकी position क्या है?" वे भी नहीं जानते, तो वे आगे पूछते हैं... जब तक सवाल पहले व्यक्ति तक नहीं पहुँचता, जो बस जानता है: "मैं 1st हूँ।"
अब answers वापस बहते हैं: 1st, तो 2nd, तो 3rd... आप तक: 8th। एक सवाल नीचे पास हुआ, answers वापसी में बने। यही recursion है, इसके stopping person समेत।
Theory
दो mandatory parts
हर correct recursive function के exactly दो parts होते हैं:
- Base case: एक इतना छोटा input कि function सीधे जवाब देता है, बिना ख़ुद को call किए। वह व्यक्ति जो जानता है वे 1st हैं।
- Recursive case: problem को एक step कम कीजिए और छोटे टुकड़े पर ख़ुद को call कीजिए।
Factorial के लिए (n! = n × (n-1) × ... × 1):
- Base:
fact(1) = 1 - Recursive:
fact(n) = n × fact(n-1)
कोई base case नहीं, या एक step जो इसकी तरफ़ कभी नहीं सिकुड़ता, और calls कभी नहीं रुकतीं।
Practical
Factorial, self-reference की चार lines
#include <iostream>
using namespace std;
long fact(int n) {
if (n <= 1) // BASE CASE: answer directly
return 1;
return n * fact(n - 1); // RECURSIVE CASE: smaller problem
}
int main() {
cout << fact(4) << endl; // 24
return 0;
}
Theory
Trace, call stack पर
Calls base case तक ऊपर ढेर होती हैं, फिर results नीचे return होते हैं:
fact(4)
fact(3)
fact(2)
fact(1) → 1 (base case reached)
2 × 1 → 2
3 × 2 → 6
4 × 6 → 24
हर pending call memory में call stack पर wait करती है: fact(4) fact(3) के return होने से पहले ख़त्म नहीं हो सकता। नीचे जाते हुए push, वापस आते हुए pop: stack lesson का LIFO, आपके programs को अंदर से चलाते हुए।
Think first
ख़ुद एक trace कीजिए
वही function इस्तेमाल करते हुए, कागज़ पर fact(5) trace कीजिए: calls की chain base case तक लिखिए, फिर वापसी में multiplications। Final value क्या है, और कौन सा call सबसे पहले ख़त्म होता है?
Show the answer
Calls: fact(5) → fact(4) → fact(3) → fact(2) → fact(1)।
Returns: 1, फिर 2×1=2, 3×2=6, 4×6=24, 5×24=120।
सबसे पहले ख़त्म होने वाला call fact(1) है, base case: सबसे LAST call सबसे FIRST return होता है। अगर यह जाना-पहचाना लगता है, लगना चाहिए: Last In, First Out, call stack वही कर रहा है जो stacks करते हैं।
Quiz
एक student लिखता है: long fact(int n) { return n * fact(n - 1); } बिना किसी if के। fact(4) run होने पर क्या होता है?
- Calls कभी नहीं रुकतीं, call stack भर जाता है, और program crash होता है (stack overflow)
- यह फिर भी 24 return करता है; base case optional है
- Compile error: recursion को एक if statement चाहिए
- यह 0 return करता है क्योंकि fact(0) आख़िर में पहुँच जाता है
Show the answer
Calls कभी नहीं रुकतीं, call stack भर जाता है, और program crash होता है (stack overflow)
Base case के बिना chain 4, 3, 2, 1, 0, -1, -2... हमेशा के लिए चलती है, हर call तब तक एक नया frame stack करती है जब तक memory ख़त्म नहीं हो जाती: stack overflow। यह ठीक compile होता है (compiler आपकी logic check नहीं करता), तो option C बाहर है। Option D लुभाता है क्योंकि fact(0) तक पहुँचा जाता है, पर वहाँ कुछ नहीं रुकता: code fact(-1) call करता रहता है। Base case decoration नहीं है, यह brakes है।
Watch out
Exam precision: recursion बनाम iteration
Classic 5-marker differences माँगता है। इनसे score कीजिए:
- Recursion: छोटा code, self-similar problems के लिए natural (trees, Tower of Hanoi), पर हर call stack memory और call overhead लेता है।
- Iteration (loops): कभी-कभी ज़्यादा code, पर कोई stack growth नहीं।
- हर recursion को iteration में फिर लिखा जा सकता है; उल्टा भी सच है।
और recursion define करते समय दोनों parts (base case, recursive case) नाम देना कभी मत भूलिए।
Theory
जहाँ recursion natural language है
Folders के अंदर folders, दो lessons आगे वाले tree structures, quicksort और mergesort जो आप बाद के semesters में मिलेंगे, JSON parsing: सब self-similar, सब naturally recursive। जब problem अपनी ही एक छोटी copy रखती है, recursion कोई trick नहीं है, यह honest description है।
Summary
Key takeaways
- Recursion: एक function एक छोटे input पर ख़ुद को call करता है जब तक एक base case सीधे जवाब न दे।
- दो mandatory parts: base case (brakes) और recursive case (छोटा step)।
- fact(4): calls 4,3,2,1 ऊपर stack होती हैं और results उल्टे return होते हैं: 1,2,6,24।
- हर pending call call stack पर एक frame के रूप में रहती है: नीचे जाते हुए push, वापस आते हुए pop (LIFO)।
- Missing base case = stack overflow crash, compile error नहीं।
- Recursion छोटे, self-similar code के लिए stack memory trade करता है; loops उल्टा trade करते हैं।
- Memory hook: queue के नीचे तब तक पूछना जब तक किसी को पता न हो।