डेटा संरचनाओं में पुनरावर्तन के सिद्धांत

रिकर्सन एक प्रक्रिया है जिसके द्वारा एक फ़ंक्शन स्वयं को कॉल करता है। हम बड़ी समस्या को छोटी उप-समस्याओं में हल करने के लिए रिकर्सन का उपयोग करते हैं। एक बात हमें ध्यान में रखनी है, कि यदि प्रत्येक उप-समस्या एक ही प्रकार के पैटर्न का अनुसरण कर रही है, तभी हम पुनरावर्ती दृष्टिकोण का उपयोग कर सकते हैं।

एक पुनरावर्ती फ़ंक्शन के दो अलग-अलग भाग होते हैं। बेस केस और रिकर्सिव केस। बेस केस का उपयोग आवर्ती के कार्य को समाप्त करने के लिए किया जाता है। यदि आधार मामला परिभाषित नहीं है, तो फ़ंक्शन अनंत बार (सैद्धांतिक रूप से) पुनरावृत्ति करेगा।

कंप्यूटर प्रोग्राम में, जब हम एक फ़ंक्शन को कॉल करते हैं, तो प्रोग्राम काउंटर का मान फ़ंक्शन क्षेत्र में कूदने से पहले आंतरिक स्टैक में संग्रहीत किया जाता है। कार्य पूरा करने के बाद, यह पता पॉप आउट करता है और इसे प्रोग्राम काउंटर में असाइन करता है, फिर कार्य को फिर से शुरू करता है। पुनरावर्ती कॉल के दौरान, यह पते को कई बार संग्रहीत करेगा, और अगले फ़ंक्शन कॉल स्टेटमेंट में कूद जाएगा। यदि एक आधार मामला परिभाषित नहीं है, तो यह बार-बार पुनरावृत्ति करेगा, और पते को स्टैक में संग्रहीत करेगा। यदि स्टैक में अब कोई स्थान नहीं है, तो यह "आंतरिक स्टैक ओवरफ़्लो" के रूप में एक त्रुटि उत्पन्न करेगा।

पुनरावर्ती कॉल का एक उदाहरण किसी संख्या का भाज्य ज्ञात करना है। हम देख सकते हैं कि एक संख्या n =n का भाज्य! n * (n-1)! के समान है, फिर से यह n * (n - 1) * (n - 2)! के समान है। तो अगर फ़ैक्टोरियल एक फ़ंक्शन है, तो इसे बार-बार बुलाया जाएगा, लेकिन तर्क 1 से कम हो गया है। जब तर्क 1 या 0 है, तो यह वापस आ जाएगा। यह रिकर्सन का आधार मामला हो सकता है। पी>

उदाहरण

#include<iostream>
using namespace std;
long fact(long n){
   if(n <= 1)
   return 1;
   return n * fact(n-1);
}
main(){
   cout << "Factorial of 6: " << fact(6);
}

आउटपुट

Factorial of 6: 720