సూత్రం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ ఇన్ఫోసిస్ మాక్య్
సూత్రం స్టాక్ థియరీ

పునరావృతం అంటే ఏమిటి?

పునరావృతం అనేది ఒక ఫంక్షన్ అని పిలుస్తుంది. ఇది పెద్ద సమస్యను లెక్కించడానికి గతంలో పరిష్కరించిన ఉప సమస్యలను ఉపయోగిస్తుంది.

ఇది ప్రోగ్రామింగ్‌లో చాలా ముఖ్యమైన మరియు గమ్మత్తైన భావనలలో ఒకటి, అయితే మేము కొన్ని నిజమైన ఉదాహరణలతో పునరావృతంతో సంబంధం కలిగి ఉండటానికి ప్రయత్నిస్తే దాన్ని సులభంగా అర్థం చేసుకోవచ్చు:

ఉదాహరణ

మీరు అద్దం ముందు అద్దం ఉంచినప్పుడు పరిస్థితి గురించి ఆలోచిస్తున్నారా?

సూత్రం

ఇది జరుగుతుంది ఎందుకంటే అద్దం అద్దం ప్రతిబింబిస్తుంది, ఇది అద్దం ప్రతిబింబిస్తుంది,….

పునరావృతం చేస్తుంది.

ఇప్పుడు పునరావృతం ఎలా పనిచేస్తుందో visual హించుకోవడానికి ప్రయత్నిద్దాం:

ఒక త్రిభుజాన్ని దాని ప్రతి అంచున గీయడానికి మేము ఒక ఫంక్షన్‌ను నిర్వచించినట్లయితే. ఫలిత సంఖ్యను మీరు Can హించగలరా?సూత్రం

పై రెండు ఉదాహరణలలో మనం ఎప్పటికీ అంతం కాని ఉప సమస్యలను చూశాము (అద్దాలు ఒకదానికొకటి ప్రతిబింబిస్తూనే ఉంటాయి మరియు అనంతమైన అద్దాలు ఉన్నట్లు కనిపిస్తాయి మరియు రెండవ ఉదాహరణలో, ఈ సంఖ్య అనంతంగా పెరుగుతూనే ఉంటుంది).

దీని ద్వారా, ఈ అనంతమైన నిర్మాణాన్ని నివారించే ప్రతి పునరావృత ఫంక్షన్ కోసం ముగింపు స్థితిని కలిగి ఉండవలసిన అవసరాన్ని మేము అర్థం చేసుకున్నాము. ఈ పరిస్థితిని అంటారు బేస్ కేసు.

పునరావృతం ఏర్పడటానికి దశలు

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

పునరావృతంపై పునరావృత్తిని ఎప్పుడు ఉపయోగించాలి

రెండు విధానాలకు వారి స్వంత లాభాలు ఉన్నాయి, అందువల్ల ఒక నిర్దిష్ట సమస్యను పరిష్కరించడానికి ఏది ఉపయోగించాలో అర్థం చేసుకోవాలి.

యొక్క సమస్యలను పరిష్కరించడానికి పునరావృత అనేది మరింత స్పష్టమైన విధానం విభజించు పాలించు విలీన క్రమబద్ధీకరణ వంటిది, మేము సమస్యను దాని ఉప-సమస్యలుగా పునరావృతంగా విచ్ఛిన్నం చేస్తూనే ఉంటాము, ఇది పునరావృత విధానాన్ని ఉపయోగించడం కొన్నిసార్లు కష్టం, ఉదాహరణకు, చెట్టు ట్రావెర్సల్(ఇనార్డర్, ప్రీఆర్డర్, పోస్టార్డర్). బహుళ ఫంక్షన్ కాల్స్ యొక్క ఓవర్ హెడ్ లేనందున పునరావృత విధానం పునరావృతం కంటే వేగంగా ఉంటుంది.

గమనిక: సమస్యను పరిష్కరించడానికి మేము పునరావృతం లేదా పునరావృతం లేదా రెండింటినీ ఉపయోగించవచ్చు.

పునరావృతం స్పష్టమైన కాల్ స్టాక్‌తో పునరావృతం ద్వారా భర్తీ చేయవచ్చు, పునరావృతం తోక_ప్రక్రియతో భర్తీ చేయవచ్చు. ప్రోగ్రామర్‌గా మనం మెమరీ మరియు టైమ్ ఆప్టిమైజేషన్‌తో సులభంగా మరియు శుభ్రంగా కోడ్ రాయడం మధ్య సమతుల్యాన్ని సృష్టించాలి.

మరొక ప్రశ్నను పరిష్కరించడానికి ప్రయత్నిద్దాం:

N యొక్క కారకాన్ని లెక్కించండి.

సి ++ అమలు

#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

చదివినందుకు ధన్యవాదములు!!

వేచి ఉండండి మరియు ఇతర బ్లాగులను కూడా చూడండి. ఏదైనా దిద్దుబాట్లు / సలహాల కోసం వ్యాఖ్యానించండి.

ప్రస్తావనలు