पुनरावृत्ती


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन इन्फोसिस एमक्यू
पुनरावृत्ती स्टॅक सिद्धांत

रिकर्शन म्हणजे काय?

रिकर्सन फक्त कॉलिंग फंक्शन म्हणून परिभाषित केले जाते. मोठ्या समस्येचे गणन करण्यासाठी हे आधीचे निराकरण केलेले उप-समस्या वापरते.

प्रोग्रामिंगमधील ही सर्वात महत्वाची आणि अवघड संकल्पना आहे परंतु आम्ही काही वास्तविक उदाहरणांसह पुनरावृत्तीशी संबंधित प्रयत्न केला तर आम्ही ते सहजपणे समजू शकतो:

उदाहरण

जेव्हा आपण आरशासमोर आरश ठेवतो तेव्हा एखाद्या परिस्थितीचा विचार करा?

पुनरावृत्ती

हे घडते कारण आरसा प्रतिबिंबित करतो, जो आरसा प्रतिबिंबित करतो, इत्यादी.

हेच पुनरावृत्ती करते.

आता रिकर्सन कसे कार्य करते ते व्हिज्युअल करण्याचा प्रयत्न करूया:

जर आपण फंक्शनच्या प्रत्येक काठावर त्रिकोण काढण्यासाठी परिभाषित केले तर. आपण परिणामी आकृतीची कल्पना करू शकता?पुनरावृत्ती

वरील दोन्ही उदाहरणांमध्ये आम्ही कधीही न संपणा sub्या उप-समस्या पाहिल्या (आरसे एकमेकांना प्रतिबिंबित करत राहतील आणि असंख्य आरसा दिसतील आणि दुसर्‍या उदाहरणात, आकृती अनंत वाढत जाईल).

याद्वारे, आम्हाला प्रत्येक रिकर्सिव्ह फंक्शनची शेवटची स्थिती असण्याची आवश्यकता समजते जी ही अनंत रचना टाळेल. ही स्थिती म्हणून ओळखली जाते बेस केस

पुनरावृत्ती बनवण्याच्या चरण

  1. बेस केस
  2. लहान समस्येसाठी रिकर्सिव्ह कॉल
  3. सोडवलेल्या उप-समस्यांचा वापर करून मोठ्या समस्येची गणना

चला हे एका उदाहरणासह समजून घेण्याचा प्रयत्न करू:

शोधः 1 सह प्रारंभ होणार्‍या सलग n नैसर्गिक संख्येच्या बेरीजची गणना करा.

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
    }
}

पुनरावृत्तीवर पुनरावृत्ती कधी वापरायची

दोन्ही दृष्टिकोनांचे स्वत: चे साधक आणि बाधक आहेत, म्हणूनच एखाद्या विशिष्ट समस्येचे निराकरण करण्यासाठी कोणता वापर केला पाहिजे हे समजणे आवश्यक आहे.

च्या समस्या सोडविण्यासाठी रिकर्सीव्ह हा अधिक अंतर्ज्ञानी दृष्टीकोन आहे विभाजित आणि विजय विलीनीकरण क्रमवारी जसे की आम्ही पुनरावृत्तीच्या पुनरावृत्तीने त्याच्या उप-समस्यांमध्ये अडचण ठेवू शकतो जे कधीकधी पुनरावृत्ती दृष्टिकोन वापरुन करणे कठीण असते, उदाहरणार्थ, वृक्ष आडवे(ऑर्डर, प्रीऑर्डर, पोस्टऑर्डर). परंतु हे देखील खरे आहे की मल्टीपल फंक्शन कॉलचे कोणतेही ओव्हरहेड नसल्यामुळे पुनरावृत्ती करण्याच्या पद्धतीचा वेग पुनरावृत्तीपेक्षा वेगवान आहे.

टीप: समस्येचे निराकरण करण्यासाठी आम्ही पुनरावृत्ती किंवा पुनरावृत्ती किंवा दोन्ही वापरू शकतो.

पुनरावृत्ती पुनरावृत्तीद्वारे स्पष्ट कॉल स्टॅकसह पुनर्स्थित केली जाऊ शकते, तर पुनरावृत्ती टेल_रेक्‍यूजन सह बदलली जाऊ शकते. आम्ही प्रोग्रामर म्हणून मेमरी आणि टाइम ऑप्टिमायझेशनसह कोडचे सहज आणि स्वच्छ लेखन दरम्यान संतुलन तयार केले पाहिजे.

दुसरा प्रश्न सोडवण्याचा प्रयत्न करूया:

एन च्या फॅक्टोरियलची गणना करा.

सी ++ अंमलबजावणी

#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

वाचल्याबद्दल धन्यवाद!!

रहा आणि इतर ब्लॉग्ज देखील पहा. कोणत्याही दुरुस्त्या / सूचनांसाठी खाली टिप्पणी द्या.

संदर्भ