Сэтгэгдэл бичих


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Infosys MAQ
Сэтгэгдэл бичих Stack Онол

Рекурс гэж юу вэ?

Рекурсия гэдэг нь өөрөө өөрийгөө дуудах функц гэж тодорхойлогдоно. Энэ нь өмнө нь шийдсэн дэд асуудлуудаа ашиглан илүү том тооцоолол хийдэг.

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

Жишээ нь

Толин тусгал толины өмнө толь тавьдаг байсан нөхцөл байдлын талаар бодоод үз дээ?

Сэтгэгдэл бичих

Толин тусгал нь толин тусгалыг тусгаж байгаа тул энэ нь тохиолддог, ... гэх мэт.

Энэ бол рекурсийг яг хийдэг.

Одоо рекурс хэрхэн ажилладагийг төсөөлөхийг хичээцгээе.

Хэрэв бид гурвалжныг ирмэг болгон зурах функцийг тодорхойлбол. Үр дүнгийн талаар та төсөөлж байна уу?Сэтгэгдэл бичих

Дээрх жишээнүүдийн аль алинд нь бид эцэс төгсгөлгүй дэд асуудлуудыг олж харсан (толин тусгалууд бие биенээ тусгасаар байх болно, мөн хязгааргүй олон толь байх шиг байна, хоёрдахь жишээнд зураг нь хязгааргүй өссөөр байх болно).

Үүгээр бид энэхүү хязгааргүй бүтцээс зайлсхийх рекурсив функц бүрийн төгсгөлийн нөхцөлтэй байх шаардлагатайг ойлгож байна. Энэ нөхцлийг дараах байдлаар мэддэг Үндсэн хэрэг.

Рекурс үүсгэх үе шатууд

  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

    }

}

Давталт ба стек

A үйл ажиллагаа гэж нэрлэдэг бөгөөд энэ нь санах ойг эзэлдэг стек функцын гүйцэтгэлийн талаархи дэлгэрэнгүй мэдээллийг хадгалах. Функц дуусахад түүний эзэмшдэг санах ой бас суллагдана. Одоо рекурс дээр функцийг өөрсдөө нэрлэдэг. Тиймээс функцын дуудлага бүрт стек дээр санах ойн блок үүсч, одоо гүйцэтгэж байгаа функцын мэдээллийг агуулдаг. Функц дууссаны дараа гадна функцэд бичигдсэн дуудлагын мэдэгдэлд буцаж ирдэг, өөрөөр хэлбэл зогссон газраасаа гадна функцийг үргэлжлүүлнэ. Дээрх жишээн дээр санах ойн бүтцийг n = 3 гэж үзье.

Рекурс ба стекийн холбоог санаж байхын тулд Base Case байхгүй тохиолдолд 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. Сүүлд давтагдах
    • Функцийн хамгийн сүүлийн гүйцэтгэсэн мэдэгдэл бол рекурсив дуудлага юм.
    • Стек дээр зөвхөн сүүлчийн рекурсив дуудлагыг хадгалах боломжтой.
    • Жишээ нь:
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
    }
}

Давталтын үед рекурсийг хэзээ ашиглах вэ

Энэ хоёр хандлага нь өөр өөрийн давуу болон сул талуудтай тул тодорхой асуудлыг шийдвэрлэхийн тулд алийг нь ашиглах ёстойг ойлгох шаардлагатай болно.

Рекурсив нь асуудлыг шийдвэрлэхэд илүү хялбар байдаг Хувааж, байлдан дагуул merge sort гэх мэт тул асуудлыг давтагдах асуудлууд болгон давтаж давтаж давтаж давтах аргыг ашиглах нь заримдаа хэцүү байдаг, жишээлбэл, Мод хөндлөн гарах(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

Уншсанд баярлалаа !!

Бидэнтэй хамт байгаарай, бусад блогуудыг бас үзээрэй. Аливаа залруулга / зөвлөмжийн талаар сэтгэгдэл үлдээнэ үү.

Ашигласан материал