Ռեկուրսիա


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Infosys MAQ
Ռեկուրսիա Գրապահոց տեսություն

Ի՞նչ է հետընթացը:

Վերադարձը պարզապես սահմանվում է որպես իրեն կոչող գործառույթ: Այն օգտագործում է իր նախկինում լուծված ենթախնդիրները `ավելի մեծ խնդիր հաշվարկելու համար:

Դա ծրագրավորման ամենակարևոր և խրթին հասկացություններից մեկն է, բայց մենք այն կարող ենք հեշտությամբ հասկանալ, եթե փորձենք հետադարձ կապը կապել որոշ իրական օրինակների հետ.

Օրինակ

Մտածեք մի իրավիճակ, երբ հայելի եք դնում հայելու առաջ:

Ռեկուրսիա

Դա տեղի է ունենում այն ​​պատճառով, որ հայելին արտացոլում է հայելին, որն արտացոլում է հայելին… և այլն:

Սա հենց այն է, ինչ անում է կրկնությունը:

Այժմ փորձենք պատկերացնել, թե ինչպես է աշխատում հետադարձումը.

Եթե ​​մենք սահմանենք մի ֆունկցիա, որի յուրաքանչյուր եզրին պետք է նկարել եռանկյուն: Պատկերացնու՞մ եք ստացված ցուցանիշը:Ռեկուրսիա

Վերոնշյալ երկու օրինակներում էլ մենք տեսանք անվերջանալի ենթախնդիրները (հայելիները կշարունակեն արտացոլել միմյանց, և թվում է, որ կա անսահման թվով հայելիներ, իսկ երկրորդ օրինակում ցուցանիշը կշարունակի աճել անվերջ):

Դրանով մենք հասկանում ենք յուրաքանչյուր ռեկուրսիվ գործառույթի համար վերջնական պայման ունենալու անհրաժեշտությունը, որը կխուսափի այս անսահման կառուցվածքից: Այս պայմանը հայտնի է որպես Բազային գործ.

Քայլեր ռեկուրսիայի ձևավորման համար

  1. Բազային գործ
  2. Ռեկուրսիվ կոչ `ավելի փոքր խնդրի համար
  3. Լուծված ենթախնդիրների օգտագործմամբ ավելի մեծ խնդրի հաշվարկ

Փորձենք դա հասկանալ օրինակով.

Հարց. Հաշվարկեք n անընդմեջ բնական թվի հանրագումարը `սկսած 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-ի համար.

Մտքում պահելով հետադարձ կապի և կապի միացումը ՝ մենք հեշտությամբ կարող ենք հասկանալ, որ Base Case- ի բացակայության դեպքում Stack- ի արտահոսքի և ժամկետի գերազանցման դեպքում մեր ծրագիրը կտուժի:

Տարբերություն ուղղակի և անուղղակի հետադարձի միջև

Ուղղակի հետադարձում

  1. Երբ նույն ֆունկցիան իրեն անվանում է, ապա այն հայտնի է որպես Ուղղակի հետադարձում.
  2. Direct Recursion- ում և՛ զանգահարելը, և՛ կանչված գործառույթը նույնն են:
  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. Պոչավոր ռեկուրսիա
    • Երբ գործառույթի վերջին կատարված հայտարարությունը ռեկուրսիվ զանգն է:
    • Հնարավոր է դեղի վրա պահել միայն վերջին ռեկուրսիվ զանգը:
    • Example:
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. Անպոչ ռեկուրսիա
    • Երբ ռեկուրսիվ զանգի հայտարարությունից հետո գործառույթում մնում են հայտարարություններ:
    • Ռեկուրսիվ զանգը կմնա շարքում մինչև դրա գնահատման ավարտը:
    • Example:
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- ով: Մենք ՝ որպես ծրագրավորող, պետք է հավասարակշռություն ստեղծենք հիշողության հետ կոդի հեշտ և մաքուր գրման և ժամանակի օպտիմալացման միջև:

Փորձենք լուծել մեկ այլ հարց.

Հաշվի՛ր n- ի գործակիցը:

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

Java- ի իրականացում

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

Շնորհակալություն կարդալու համար:

Մնացեք լարված և դիտեք նաև մյուս բլոգերը: Մեկնաբանեք ցանկացած շտկման / առաջարկի համար:

Սայլակ