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

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

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

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

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

उदाहरण

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

आउटपुट

Factorial of 6: 720