Recursion


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना इंफोसिस MAQ
Recursion धुआँरा सिद्धांत

क्या है रिकर्सन?

रिकर्सियन को केवल एक फ़ंक्शन के रूप में परिभाषित किया जाता है। यह एक बड़ी समस्या की गणना करने के लिए अपनी पहले से हल की गई उप-समस्याओं का उपयोग करता है।

यह प्रोग्रामिंग में सबसे महत्वपूर्ण और मुश्किल अवधारणाओं में से एक है, लेकिन हम इसे आसानी से समझ सकते हैं यदि हम वास्तविक वास्तविक अनुभव के साथ पुनरावर्तन से संबंधित होने का प्रयास करते हैं:

उदाहरण

उस स्थिति के बारे में सोचें जब आप दर्पण के सामने दर्पण रखते हैं?

Recursion

ऐसा इसलिए होता है क्योंकि एक दर्पण दर्पण को प्रतिबिंबित कर रहा है, जो दर्पण को प्रतिबिंबित कर रहा है, और इसी तरह।

यह वही है जो पुनरावृत्ति करता है।

आइए अब यह देखने की कोशिश करें कि पुनरावृत्ति कैसे काम करती है:

अगर हम किसी फ़ंक्शन को उसके हर किनारे पर एक त्रिकोण बनाने के लिए परिभाषित करते हैं। क्या आप परिणामी आकृति की कल्पना कर सकते हैं?Recursion

उपरोक्त दोनों उदाहरणों में हमने कभी न खत्म होने वाली उप-समस्याओं को देखा (दर्पण एक दूसरे को दर्शाते रहेंगे और वहाँ अनंत संख्या में दर्पण दिखाई देते हैं और दूसरे उदाहरण में यह आंकड़ा अनंत रूप से बढ़ता रहेगा)।

इसके द्वारा, हम हर पुनरावर्ती कार्य के लिए एक अंतिम स्थिति होने की आवश्यकता को समझते हैं जो इस अनंत संरचना से बचती है। इस स्थिति के रूप में जाना जाता है बेस केस।

पुनरावर्तन बनाने के चरण

  1. मुख्य मामला
  2. छोटी समस्या के लिए पुनरावर्ती कॉल
  3. हल उप-समस्याओं का उपयोग करके बड़ी समस्या की गणना

आइए इसे एक उदाहरण से समझने की कोशिश करें:

प्रश्न: 1 के साथ शुरू होने वाले लगातार प्राकृतिक संख्या के योग की गणना करें।

int sum(int n){

    // Base Case

    if(n==1){

        return n;

    }

    else{

        int smallerSum=sum(n-1);      //recursive call for smaller problem

        return n+smallerSum;         // solve bigger problem using solved smaller sub-problems

    }

}

पुनरावृत्ति और ढेर

जब समारोह कहा जाता है, यह स्मृति में व्याप्त है धुआँरा फ़ंक्शन के निष्पादन के बारे में विवरण संग्रहीत करने के लिए। और जब फ़ंक्शन समाप्त होता है, तो इसके द्वारा कब्जा की गई मेमोरी भी जारी की जाती है। अब पुनरावृत्ति में, जैसा कि हम जानते हैं कि एक फ़ंक्शन अपने आप में कहा जाता है। इसलिए प्रत्येक फ़ंक्शन कॉल पर, स्टैक में मेमोरी का एक ब्लॉक बनाया जाता है, जो वर्तमान में निष्पादित फ़ंक्शन की जानकारी रखता है। जब फ़ंक्शन समाप्त होता है, तो यह बाहरी फ़ंक्शन में लिखे गए कॉलिंग स्टेटमेंट पर लौटता है यानी, एक बाहरी फ़ंक्शन को फिर से शुरू किया जाता है जहां से यह बंद हो गया है। चलो n = 3 के लिए उपरोक्त उदाहरण में स्मृति संरचना देखें:

पुनरावृत्ति और स्टैक के संबंध को ध्यान में रखते हुए, हम आसानी से समझ सकते हैं कि बेस केस की अनुपस्थिति में, हमारा कार्यक्रम स्टैक अतिप्रवाह और समय सीमा पार होने के साथ पीड़ित होगा।

प्रत्यक्ष और अप्रत्यक्ष पुनरावृत्ति के बीच अंतर

डायरेक्ट रिक्रिएशन

  1. जब एक ही फ़ंक्शन कॉल करता है तो इसे के रूप में जाना जाता है डायरेक्ट रिक्रिएशन.
  2. डायरेक्ट रिक्रिएशन में, कॉलिंग और फंक्शन दोनों एक ही है।
  3. इसमें एक-चरण पुनरावर्ती कॉल होगा।

डायरेक्ट रिकर्सिव फ़ंक्शन की कोड संरचना:

return_type func_name(arguments)
{
  // some code...

  func_name(parameters);

  // some code...
}

अप्रत्यक्ष पुनरावर्तन

  1. जब कोई फ़ंक्शन किसी अन्य फ़ंक्शन को कॉल करता है, जो अपने मूल फ़ंक्शन को भी प्रत्यक्ष या अप्रत्यक्ष रूप से कॉल कर रहा है, तो इसे इस रूप में जाना जाता है अप्रत्यक्ष पुनरावर्तन।
  2. इनडायरेक्ट रिकर्सनशन में, कॉलिंग और कॉलिंग फ़ंक्शन अलग-अलग हैं।
  3. एक बहु-चरण पुनरावर्ती कॉल होगा।

अप्रत्यक्ष पुनरावर्ती फ़ंक्शन की कोड संरचना:

return_type func_name1(arguments)
{
  // some code...

  func_name2(parameters);

  // some code...
}

return_type func_name2(arguments)
{
  // some code...

  func_name1(parameters);

  // some code...
}

रिकर्सन के प्रकार

  1. पुर्नजन्म हुआ
    • जब किसी फ़ंक्शन का अंतिम निष्पादित विवरण पुनरावर्ती कॉल होता है।
    • स्टैक पर केवल अंतिम पुनरावर्ती कॉल को रखना संभव है।
    • उदाहरण:
int sum(int n,int &ans){
    if(n==0){
        return ans;
    }
    else{
        ans=ans+n;
        return sum(n-1,ans);     // last statement to be executed is recursive call

    }
}
  1. गैर-पूंछ वाली पुनरावृत्ति
    • जब पुनरावर्ती कॉल स्टेटमेंट के बाद निष्पादित करने के लिए फ़ंक्शन में बचे हुए कथन होते हैं।
    • पुनरावर्ती कॉल इसके मूल्यांकन के अंत तक स्टैक में रहेगा।
    • उदाहरण:
int sum(int n){
    if(n==1){
        return n;
    }
    else{
        int smallerSum=sum(n-1);      //recursive call for smaller problem
        return n+smallerSum;         //statements to be executed after recursive call
    }
}

पुनरावृत्ति पर पुनरावृत्ति का उपयोग कब करें

दोनों दृष्टिकोणों के पास अपने स्वयं के पेशेवरों और विपक्ष हैं, इसलिए यह समझना आवश्यक हो जाता है कि किसी विशेष समस्या को हल करने के लिए किसका उपयोग किया जाना चाहिए।

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

नोट: एक समस्या को हल करने के लिए हम पुनरावृत्ति या पुनरावृत्ति या दोनों का उपयोग कर सकते हैं।

पुनरावृत्ति को एक स्पष्ट कॉल स्टैक के साथ पुनरावृत्ति द्वारा प्रतिस्थापित किया जा सकता है, जबकि पुनरावृत्ति को tail_recursion से बदला जा सकता है। हमें एक प्रोग्रामर के रूप में स्मृति और समय अनुकूलन के साथ कोड के आसान और स्वच्छ लेखन के बीच एक संतुलन बनाना चाहिए।

आइए एक और सवाल हल करने की कोशिश करें:

एन के भाज्य की गणना करें।

C ++ कार्यान्वयन

#include <iostream>
using namespace std;
int fact(int n){
   // Base Case
   if (n <= 1)
        return 1;
   else 
       return n*fact(n-1);    
}
int main(){
   int n=5;
   cout<<fact(n);
   return 0;
}
Output: 15

जावा कार्यान्वयन

class Main{  
 static int fact(int n){    
  if (n<=1)    
    return 1;    
  else    
    return(n * fact(n-1));    
 }    
 public static void main(String args[]){  
  int n=5;   
  System.out.println(fact(n));    
 }  
}
Output: 15

पढ़ने के लिए धन्यवाद!!

बने रहें और अन्य ब्लॉग भी देखें। किसी भी सुधार / सुझाव के लिए नीचे टिप्पणी करें।

संदर्भ