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

fib(int);
int main()
{
// Foydalanuvchidan Fibonacci qatori indeksini so'rash
cout << "Fibonacci sonining indeksini kiriting: ";
int index;
cin >> index;

// Fibonaccini chop etish

cout << index << "-chi indeksdagi Fibonacci son "
<< fib(index) << " ga teng!" <

return 0;

}
// Fibonacci sonini aniqlash funksiyasi
int fib(int index)
{
if (index == 0) // Bazaviy holat
return 0;
else if (index == 1) // Bazaviy holat
return 1;
else // rekursiv chaqirish
return fib(index - 1) + fib(index - 2);
}

Yuqoridagi dasturda bajarilgan hisoblashlar qanday kechayotganini qo‘rish qiyin. Quyida keltirilgan rasmda fib(4) holat uchun rekursiv chaqiruvlarning ketma-ketligi ko‘rib chiqilgan. Boshlang‘ich fib(4) funksiya ikkita rekursiv chaqiruvni amalga oshiradi fib(3) va fib(2), undan keyin fib(3)+fib(2) natijasi qaytariladi. Rasmdagi nishonlar funksiyaning chaqirilish ketma-ketligini ko‘rsatmoqda.

Rasmda ko‘rganingizdek, ko‘plab qaytariluvchi rekursiv chaqiruvlar amalga oshirilgan. Masalan: fib(2) olat uchun rekursiv chaqiruvlarning ketma-ketligi ko‘rib chiqilgan. Boshlang‘ich fib(4) ikki marotaba chaqirilgan, fib(1) uch marotaba, fib(0) esa ikki marotaba. Umuman olganda fib(indeks) ni hisoblash uchun fib(indeks-1)ga qaraganda ikki marotaba ko‘proq rekursiv chaqiruvlar amalga oshiriladi. Indeks qiymatini oshirganingiz sari, chaqiruvlar soni ham bir qancha oshib boradi, quyidagi jadvaldagiday.

indeks	2 3 4 10 20 30 40 50
Chaqiruvlar soni	3 5 9 177 21891 2.692.537 331.160.281 2.075.316.483