Theory
जो function खुद को फ़ोन करता है
अब तक हर function ने दूसरों को call किया। C कुछ अजीब की इजाज़त देता है: एक function खुद को call करता हुआ।
पहली प्रतिक्रिया, ठीक ही: "यह तो हमेशा loop करता रहेगा।"
लगभग। एक गायब सामग्री के साथ यह सचमुच शीशों का अनंत hall है, और उस सामग्री के साथ यह इस subject की सबसे सुंदर चार lines बन जाता है: factorial, एक ऐसे function से compute होता जो ज़्यादातर काम अपनी ही एक छोटी copy पर भरोसा करके कराता है।
Theory
कतार में आगे पूछना
आप एक लंबी कतार में आख़िरी हैं और अपनी position जाननी है। आगे वाले से पूछिए: "आपकी position क्या है?" उन्हें भी नहीं पता, तो वे आगे पूछते हैं... जब तक सवाल पहले व्यक्ति तक पहुँचता है, जो बस जानता है: "मैं number 1 हूँ" (base case)। अब जवाब पीछे की तरफ बहते हैं, हर व्यक्ति एक जोड़ता है, जब तक आपका जवाब आ जाता है। एक सवाल नीचे भेजा, जवाब ऊपर बनते गए: यही recursion की पूरी machinery है।
Theory
Recursion, औपचारिक रूप से
एक recursive function को ठीक दो हिस्से चाहिए:
- Base case: सबसे छोटा input, सीधे जवाब दिया जाता, कोई आगे call नहीं। यही brake है।
- Recursive case: problem को एक छोटे self के ज़रिए फिर से कहा जाता है।
Factorial (n! = n × (n-1) × ... × 1) स्वाभाविक रूप से फिर कहा जाता है: n! = n × (n-1)! और 0! = 1:
int factorial(int n) {
if (n == 0) return 1; /* base case */
return n * factorial(n - 1); /* smaller self */
}
हर call को base case की तरफ बढ़ना चाहिए, हर बार छोटा n, वरना brake कभी नहीं पहुँचता।
Practical
Factorial, recursive और loop वाला
#include <stdio.h>
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
int main() {
int f = 1, i, n = 4;
printf("Recursive: %d\n", factorial(4));
for (i = 1; i <= n; i++) f = f * i; /* the loop twin */
printf("Loop : %d\n", f);
return 0;
}This example runs in Gri-Learn on the web, where you can edit it and see the output.
Think first
Stack को trace कीजिए
factorial(4) को कागज़ पर trace कीजिए: calls की श्रृंखला नीचे जाती हुई लिखिए, चिह्नित कीजिए कहाँ रुकती है, फिर वापस ऊपर आते नतीजों को गुणा कीजिए। क्या return होता है, और किस data structure ने रुकी हुई calls को पकड़ा?
Show the answer
नीचे: f(4) → f(3) → f(2) → f(1) → f(0), पाँच calls, हर एक रुककर इंतज़ार करती। f(0) base case पर पहुँचता है: 1। ऊपर: 1×1=1, 2×1=2, 3×2=6, 4×6=24।
रुकी हुई calls call stack पर इंतज़ार करती रहीं, last in, first out, ठीक वही LIFO structure जो BCA304 के प्रमुख lesson का है। हर recursion भेस बदले काम करता stack है।
Quiz
एक student base case मिटा देता है: int factorial(int n) { return n * factorial(n - 1); } और factorial(4) call करता है। क्या होता है?
- Calls कभी नहीं रुकतीं; call stack overflow होता है और program crash हो जाता है
- फिर भी 24 return करता है, C को factorials पता हैं
- एक compile error: base cases अनिवार्य syntax हैं
- तुरंत 0 return करता है
Show the answer
Calls कभी नहीं रुकतीं; call stack overflow होता है और program crash हो जाता है
बिना brake के, f(4), f(3) को call करता है... f(0), f(-1), f(-2), हमेशा छोटा, कभी न रुकता। हर रुकी call stack memory घेरती है जब तक वह खत्म न हो जाए: stack overflow, एक runtime crash (कोई compile error नहीं, syntax legal है)। "base case के बिना क्या होता है" अस्तित्व में recursion का सबसे पक्का सवाल है।
Quiz
Factorial, loop के रूप में और recursion के रूप में, दोनों तरह काम करता है। कौन सा statement उनकी सही तुलना करता है?
- दोनों सही हैं; loop stacked calls से बचता है, recursion स्वाभाविक रूप से nested problems पर चमकता है
- Recursion हमेशा loops से तेज़ है
- Loops 3 से ऊपर factorials compute नहीं कर सकते
- Recursion कभी अतिरिक्त memory इस्तेमाल नहीं करता
Show the answer
दोनों सही हैं; loop stacked calls से बचता है, recursion स्वाभाविक रूप से nested problems पर चमकता है
Factorial जैसी सीधी गिनती के लिए, loop उतना ही साफ़ और सस्ता है (रुकी calls का ढेर नहीं)। Recursion वहाँ अपनी कमाई करता है जहाँ problem खुद nested हो, folders के अंदर folders, Tower of Hanoi, आगे BCA304 में tree structures, जहाँ loop वाला version भद्दा हो जाता है। Tool, problem के आकार के पीछे चलता है: यही exam लायक तुलना है।
Watch out
Marks कहाँ कटते हैं
कोई base case नहीं, या ऐसा जिस तक calls कभी नहीं पहुँचतीं (factorial(n-1) के साथ n == 5 वाला base, 4 पर call): दोनों stack overflow में खत्म होते हैं, छोटा होने की दिशा जाँचिए। गलत base value: factorial(0) को 1 return करना चाहिए, 0 नहीं, एक गलत brake और उसके ऊपर का हर जवाब 0। लापरवाही से trace करना: exams नीचे-श्रृंखला और ऊपर-गुणा दोनों लिखा हुआ चाहते हैं; वापसी का सफर छोड़ने पर आधे marks जाते हैं।
Theory
क्लासिक दूसरा उदाहरण
Fibonacci (हर number पिछले दो का जोड़: 0 1 1 2 3 5 8...) recursion का दूसरा exam सितारा है: fib(n) = fib(n-1) + fib(n-2), दो base cases के साथ (fib(0)=0, fib(1)=1)। आज रात इसे लिखिए; fib(4) trace कीजिए। C में एक lesson बाकी है: struct, जहाँ हमारे student को आख़िरकार name, marks और grade एक ही record में मिलते हैं, पूरे subject का इनाम।
Summary
Key takeaways
- Recursion: एक function जो खुद को छोटे input पर call करता है।
- दो अनिवार्य हिस्से: base case (brake) + recursive case (छोटा self)।
- factorial: if (n == 0) return 1; return n * factorial(n - 1);
- रुकी calls call stack पर इंतज़ार करती हैं (LIFO); नतीजे वापसी में गुणा होते हैं।
- कोई base case नहीं → stack overflow crash; base पहुँचने लायक और सही होना चाहिए।
- सीधी गिनती के लिए loops; स्वाभाविक रूप से nested problems के लिए recursion।
- याद रखने का hook: कतार में आगे पूछो, जवाब वापस ऊपर आते हैं।