Recursion


Кыйынчылык деңгээли жеңил
Көп суралган Amazon Infosys MAQ
Recursion чөмөлө теория

Рекурсия деген эмне?

Рекурсия жөн гана өзүн чакырган функция катары аныкталат. Ал чоңураак көйгөйдү эсептөө үчүн мурда чечилген кичи маселелерин колдонот.

Бул программалоодогу эң маанилүү жана татаал түшүнүктөрдүн бири, бирок рекурсияны чыныгы мисалдар менен байланыштырууга аракет кылсак, аны оңой эле түшүнөбүз:

мисал

Күзгүнү күзгүнүн алдына койгон учурду элестетсеңиз?

Recursion

Бул күзгү күзгүнү чагылдыргандыктан, күзгү чагылдыргандыктан болот ... жана башкалар.

Дал ушул нерсе рекурсияны жасайт.

Эми рекурсия кандайча иштээрин элестетип көрөлү:

Эгерде анын ар бир четине үч бурчтук тартуу функциясын аныктасак. Натыйжада кандай натыйжага жеткенин элестете аласызбы?Recursion

Жогорудагы эки мисалда тең бүтпөс көмөкчү көйгөйлөрдү көрдүк (күзгүлөр бири-бирин чагылдырып, чексиз күзгүлөр пайда болот, экинчи мисалда көрсөткүч чексиз өсө берет).

Ушундан улам, биз ушул чексиз структурадан алыс боло турган ар бир рекурсивдик функция үчүн акыркы шарттын болушунун зарылдыгын түшүнөбүз. Бул абал белгилүү Негизги Case.

Рекурсияны түзүү кадамдары

  1. Негизги Case
  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 үчүн эс тутумун карап көрөлү:

Рекурсия жана стек ассоциациясын эсибизден чыгарбасак, Негизги Колдун жоктугунан улам, биздин программа Stack толуп, убакыттын чегинен ашып кетерин оңой эле түшүнөбүз.

Түз жана Кыйыр рекурсиянын айырмасы

Түз рекурсия

  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. Tired Recursion
    • Функциянын акыркы аткарылган оператору рекурсивдик чакыруу болгондо.
    • Стекде акыркы рекурсивдик чалууну гана сактоого болот.
    • мисал:
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
    }
}

Кайталоонун үстүнөн рекурсияны качан колдонушат

Эки ыкманын тең оң жана терс жактары бар, ошондуктан белгилүү бир көйгөйдү чечүү үчүн кайсынысын колдонуу керектигин түшүнүү зарыл болуп калат.

Рекурсивдүү - бул көйгөйлөрдү чечүү үчүн интуитивдик мамиле Бөлүп, жеңип ал Бириктирүү сыяктуу, анткени көйгөйдү рекурсивдүү түрдө чакан көйгөйлөргө бөлүп алсак болот, кээде кайталанма ыкманы колдонуу менен жасоо кыйынга турат, мисалы, Tree traversal(Inorder, Preorder, Postorder). Бирок, кайталанма ыкма рекурсияга караганда тезирээк экендиги дагы чындык, анткени бир нече функционалдык чалууларга ашыкча чыгым болбойт.

Эскертүү: Маселени чечүү үчүн биз кайталоону же рекурсияны колдоно алабыз, жада калса экөөнү тең колдоно алабыз.

Рекурсияны так чалуулар стеги менен кайталоо менен, ал эми итерацияны 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

Окуу үчүн рахмат !!

Биз менен бирге болуңуз жана башка блогдорду да карап көрүңүз. Бардык оңдоолор / сунуштар үчүн комментарий калтырыңыз.

шилтемелер