O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi farg’ona davlat universiteti fizika-matematika fakulteti

Rekurtsiya va u bilan ishlash

Funksiya o'zini o'zi chaqiradigan jarayon rekursiya, unga mos keladigan funktsiya esa rekursiv funktsiya deb nomlanadi . Rekursiyani tushunish uchun mashhur misol - bu faktorial funktsiya.

Faktorial funktsiya: f (n) = n * f (n-1), asosiy shart: agar n <= 1 bo'lsa, u holda f (n) = 1. Xavotir olmang, biz bazaviy shart nima ekanligini va nima uchun bu muhimligini muhokama qilamiz.

Quyidagi diagrammada. Faktorial funktsiya funktsiya bazaviy holatga kelguncha o'zini qanday chaqirayotganligini ko'rsatdim.

Muammoni C ++ dasturi yordamida hal qilishga imkon bering.

C ++ rekursion misoli: Faktorial

#include

using namespace std;

//Factorial function

int f(int n){

/* This is called the base condition, it is

* very important to specify the base condition

* in recursion, otherwise your program will throw

* stack overflow error.

*/

   if (n <= 1)

        return 1;

   else 

      return n*f(n-1);

}

int main(){

int num;

  cout<<"Enter a number: ";

   cin>>num;

   cout<<"Factorial of entered number: "<

return 0;

}

Natija:

Enter a number: 5

Factorial of entered number: 120

Asosiy holat

Yuqoridagi dasturda siz rekursiv funktsiyada bazaviy shartni taqdim etganimni ko'rishingiz mumkin. Shart:

if ( n <= 1 ) return 1 ;

Rekursiyaning maqsadi - asosiy shartga kelguncha muammoni kichikroq muammolarga bo'lish. Masalan, yuqoridagi faktorial dasturda f (n) faktorial funktsiyasini kichikroq f (n-1) faktorial funktsiyani chaqirish orqali hal qilyapman, bu n qiymati bazaviy holatga (f (1) = 1) yetguncha takrorlanadi. Agar siz rekursiv funktsiyada bazaviy shartni aniqlamasangiz, unda siz stack overflow xatosiga ega bo'lasiz.

To'g'ridan-to'g'ri rekursiya va bilvosita rekursiya