Recursion in C++
Recursion क्या है?
Recursion तब है जब कोई function खुद को call करता है। Loop के बजाय, function एक बड़ी समस्या को उसका थोड़ा छोटा रूप अपनी ही एक और copy को सौंपकर हल करता है — जब तक समस्या इतनी छोटी न हो जाए कि सीधे उत्तर दिया जा सके।
Base case
हर recursion को एक base case चाहिए — सरलतम input, बिना फिर call किए उत्तर दिया गया। यही श्रृंखला रोकता है। दूसरा हिस्सा, recursive case, function को एक छोटे input पर call करता है।
1) Base case — कब रुकना है। 2) Recursive case — खुद को किसी छोटी चीज़ पर call करना। Base case छूटा तो यह कभी नहीं रुकता।
उदाहरण: factorial
Factorial: 5! = 5 × 4 × 3 × 2 × 1। ध्यान दें n! = n × (n-1)! — यही recursion है।
#include <iostream>
using namespace std;
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
int main() {
cout << factorial(5) << "\n";
return 0;
}120
Calls को trace करना
यह देखना मददगार है कि calls कैसे जमा होती हैं और फिर समेटती हैं:
factorial(4) = 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * 1))
= 24Calls base case तक नीचे जाती हैं, फिर उत्तर वापस ऊपर गुणा होते हैं।
उदाहरण: Fibonacci
हर Fibonacci number पिछले दो का योग है, दो base cases के साथ:
int fib(int n) {
if (n < 2) return n; // base: fib(0)=0, fib(1)=1
return fib(n - 1) + fib(n - 2); // recursive case
}
// fib(6) → 8यह सरल Fibonacci वही values कई बार दोबारा गिनता है, तो बड़े n के लिए धीमा है। वहाँ loop या memoisation कहीं तेज़ है।
Recursion बनाम iteration
| Recursion | Iteration | |
|---|---|---|
| इस्तेमाल | Function खुद को call करता है | Loops |
| Memory | अतिरिक्त (call stack) | कम |
| किसके लिए | Trees, divide & conquer | गिनती, सरल दोहराव |
कोई भी recursive चीज़ loop से लिखी जा सकती है, और उल्टा भी — जो समस्या के लिए ज़्यादा साफ़ पढ़ा जाए वही चुनें।
आम गलतियाँ
- Base case भूलना, अनंत recursion और stack overflow पैदा करना।
- ऐसा recursive call जो base case की ओर न बढ़े।
- बड़े
nपर Fibonacci के लिए naive recursion इस्तेमाल करना (बहुत धीमा)। - Recursive call का परिणाम
returnकरना भूलना।
1 से n तक numbers का योग करने को एक recursive function लिखें, और power base^exp निकालने को दूसरा। हर एक के लिए पहले base case लिखें, फिर recursive case।
सारांश
- Recursion एक function का खुद को छोटे input पर call करना है।
- हर recursion को रुकने के लिए base case चाहिए, साथ में recursive case।
- Factorial और Fibonacci classic उदाहरण हैं।
- Recursion stack memory इस्तेमाल करता है; base case छूटने पर stack overflow होता है।
- स्वाभाविक रूप से recursive समस्याओं के लिए recursion; सरल दोहराव के लिए loops।
