Rekursiv funksiyalar to‘g‘risida bilim va ko‘nikmalarga EGA bo‘lish; Rekursiv o‘ylashni shakllantirish

Dastur kodi:
#include
using namespace std;

// faktorialni indeks bo'yicha hisoblash

int factorial(int);

int main()

{
// Foydalanuvchidan butun son kiritilishini so'rash
cout << "Iltimos manfiy bo'lmagan butun son kiriting: ";
int n;
cin >> n;

// Faktorialni chop etish

cout << n << " sonining faktoriali ==> " << factorial(n);

return 0;

}

// faktorialni indeks bo'yicha hisoblash

int factorial(int n)
{
if (n == 0) //Bazaviy holat
return 1;
else
return n * factorial(n - 1); // Rekursiv chaqirish
}


Natija:




Factorial funksiyasining (21-27 satrlarida) qaralgan jarayon matematik rekursiyaning C++ tilidagi ko‘rinigi bo‘lib, faktorialni chaqirish rekursiya bo‘lishi bu funksiya o‘zini-o‘zi chaqirishi bilan bog‘liq. Funksiyaga berilayotgan parametr qiymati 0 ga qadar kamayib boradi.
Quyidagi rasmda faktorial funksiyasining n=4 bo‘lgan holatdan chaqirilishi ko‘rsatilib o‘tilgan.


1-mashq. Kiritilgan sonning teskarisini chop etuvchi dastur kodi rekursiv funksiya yordamida tuzilsin:
Dastur kodi:

1. 
   #include
   
2. 
   using namespace std;
   
3. 
   void f(int n)
   
4. 
   {
   
5. 
   if (n > 0)
   
6. 
   {
   
7. 
   cout << n % 10;
   
8. 
   f(n / 10);
   
9. 
   }
   
10. 
    }
    
11. 
    int main()
    
12. 
    {
    
13. 
    f(1234567);
    
14. 
    return 0;
    
15. 
    }
    

Natija:



Fibonachchi sonlar. Faktorialni rekursiyasiz ham ishlash mumkin. Ayrim hollarda rekursiya yordamida tabiiy va sodda dastur tuzib masalaning Yechimini topish mumkin, hamda bunday misollarning Yechimini topish rekursiyasiz juda ham qiyinchilik tug‘diradi. Hammaga ma’lum Fibonachchi qatorini quyidagicha ko‘rib chiqamiz:
Fibonachchi qatori: 0 1 1 2 3 5 8 13 21 34 55 89 . . .
Indekslari: 0 1 2 3 4 5 6 7 8 9 10 11

Fibonachchi qatori 0 va 1 dan boshlanib, har bir keyingi sonlar o‘zidan oldingi ikki sonning yig‘indisini tashkil etadi. Fibonachchi qatorini rekursiya yordamida quyidagicha aniqlash mumkin:

fib(0) = 0;
fib(1) = 1;
fib(indeks) = fib(indeks-2) + fib(indeks-1); indeks>=2

Berilgan indeks uchun fib(indeks) ni qanday aniqlash mumkin? fib(2) aniqlash oson, chunki fib(0) va fib(1) nechiga tengligini oldindan bilamiz. Tasavvur qilamiz biz fib(indeks-2) va fib(indeks-1) ning qiymatlari bilamiz, shu holda fib(indeks) ni aniqlash oson kechadi. fib(indeks-2) va fib(indeks-1) qiymatlarini hisoblash rekursiya g‘oyasini qo‘llagan holda indekslar 0 yoki 1 ga tenglashgunga qadar amalga oshiriladi.

Bazaviy holat: indeks=0 yoki indeks=1. Agarda funksiya indeks=0 yoki indeks=1 holatda chaqirilsa funksiya natijasi darhol qaytariladi. Funksiya indeks>=0 holat uchun esa, mazkur funksiya rekursiv chaqiriluvchi 2 qism masalalar fib(indeks-2) va fib(indeks-1) ga ajratiladi. fib(indeks) ni hisoblovchi rekursiv algoritm quyidagicha yozilishi mumkin:

if (index == 0)

return 0;
else if (index == 1)
return 1;
else
return fib(index - 1) + fib(index - 2);

Quyidagi dasturda Fibonachchi qatori indeksi kiritilganda, mazkur indeksdagi Fibonachchi sonini rekursiv funksiya yordamida ekranga chop etishi ko‘rib chiqiladi.

#include
using namespace std;
// Fibonacci sonini aniqlash funksiyasi
int