वह Process जिसमें कोई function स्वयं को directly या indirectly call करता है, Recursion कहलाता है और corresponding function, Recursive function कहलाता है। Recursive function का उपयोग करके, कुछ Problem को काफी आसानी से solve किया जा सकता है।
इस तरह की problems के उदाहरण Towers of Hanoi(TOH), Inorder/Preorder/Postorder Tree traversal, DFS of Graph आदि हैं। एक recursive function स्वयं की एक copy call करके और original problems की small sub-problems को solve करके एक specific problem का solution find करता है।
आवश्यकता पड़ने पर many more recursive calls, generate की जा सकती हैं। यह जानना आवश्यक है कि इस recursion process को end करने के लिए हमें एक certain calls provide करना चाहिए। तो हम कह सकते हैं कि हर बार function original problem के simpler version के साथ स्वयं को call करता है।
Need of Recursion :
Recursion एक amazing technique है जिसकी help से हम अपने code की length को reduce कर सकते हैं और code को read और write करना easy हो जाता हैं। iteration technique पर इसके कुछ advantages हैं जिन पर बाद में discussion की जाएगी। एक task जिसे इसके समान subtask के साथ define किया जा सकता है, recursion इसके लिए सबसे अच्छे solutions में से एक है। Example के लिए; Factorial of a number।
Properties of Recursion :
1. Different input के साथ same operation को कई बार perform करना।
2. प्रत्येक step में, हम problem को smaller करने के लिए smaller input लेने का प्रयास करते हैं।
3. Recursion को रोकने के लिए Base condition की आवश्यकता होती है अन्यथा infinite loop occur होगा।
How a recursive function stored in memory :
Recursion अधिक memory use करता है, क्योंकि recursive function प्रत्येक recursive call के साथ stack में add होता है, और call finished होने तक value रखता है। recursive function stack data structure की तरह ही LIFO (LAST IN FIRST OUT) function का उपयोग करता है।
What is Base condition in recursion :
किसी भी recursive program में लागू होने वाली condition को Base condition के रूप में जाना जाता है। प्रत्येक recursive function में एक Base condition आवश्यक होती है otherwise यह एक infinite loop की तरह continue execute होती रहेगी।
int fact(int n)
{
if(n <= 1) // base case
return 1;
else
return n*fact(n-1);
}
Why stack overflow error occur in recursion :
यदि Base case reached नहीं हुआ है या defined नहीं किया गया है, तो stack overflow की problem arise हो सकती है। इसे समझने के लिए एक example लेते हैं।
int fact(int n)
{
// wrong base case (it may cause
// stack overflow).
if (n == 100)
return 1;
else
return n*fact(n-1);
}
यदि fact(10) call किया जाता है, तो यह fact (9), fact (8), fact (7) आदि को call करेगा, लेकिन number कभी भी 100 तक नहीं पहुंचेगी। इसलिए, Base case reach नहीं होगा। यदि stack पर इन functions द्वारा memory exhausted हो जाती है, तो यह stack overflow का कारण होगा।
What is the difference between Direct recursion and Indirect recursion :
Function sum() को direct recursion कहा जाता है यदि वह उसी function को sum()function द्वारा call करता है।
Function sum() को Indirect recursion कहा जाता है यदि यह किसी अन्य function को sum_new द्वारा fun sum() को directly या indirectly रूप से call करता है।
// An example of direct recursion in c++
void directRecsum()
{
// Some code....
directRecsum();
// Some code...
}
// An example of indirect recursion in c++
void indirectRecsum1()
{
// Some code...
indirectRecsum2();
// Some code...
}
void indirectRecsum2()
{
// Some code...
indirectRecsum1();
// Some code...
}
How memory is allocated to different function calls in recursion:
जब किसी Function को main () function से call किया जाता है, तो उसे stack पर memory allocate की जाती है। एक recursive function स्वयं को call करता है, calling function को allocated memory के top पर call किए गए function की memory allocate की जाती है और प्रत्येक फ़ंक्शन कॉल के लिए स्थानीय चर की एक अलग प्रति बनाई जाती है। जब Base case पहुंच जाता है, तो function अपना value उस function को return कर देता है जिसके द्वारा इसे call किया जाता है और memory को de-allocate किया जाता है और process continue रहती है।
Example : Find the factorial of a given number.
#include <iostream>
using namespace std;
int main() {
int n;
long factorial = 1.0;
cout << "Enter a positive integer: ";
cin >> n;
if (n < 0)
cout << "Error! Factorial of a negative number doesn't exist.";
else {
for(int i = 1; i <= n; ++i) {
factorial *= i;
}
cout << "Factorial of " << n << " = " << factorial;
}
return 0;
}Short notes on Recursion :
1. Recursion में दो तरह के case होते हैं recursive case और एक Base case।
2. Base case का उपयोग recursive function को terminate करने के लिए किया जाता है जब cases turn to be true.
3. प्रत्येक recursive call, stack memory में उस method की एक नई copy create करता है।
4. infinite recursion से stack memory समाप्त हो सकती है।
5. Recursive algorithm के examples: merge sort, Quick sort, Tower of Hanoi, Fibonacci series, Factorial problemsआदि।
