Ishdan maqsad: Rekursiv ma’lumot tuzilmasini toifalarini o‘rganish va ularni tadqiq qilish. Qo‘yilgan masala

Ishdan maqsad:Rekursiv ma’lumot tuzilmasini toifalarini o‘rganish va ularni tadqiq qilish.
Qo‘yilgan masala: va uning turlari haqida nazariy va amaliy bilimga ega bo’lish.
Ish tartibi:

• 
  Tajriba ishi nazariy ma’lumotlarini o‘rganish;
  
• 
  Berilgan topshiriqning algoritmini ishlab chiqish;
  
• 
  C++dasturlash muhitida dasturni ya+4ratish;
  
• 
  Natijalarni tekshirish;
  
• 
  Hisobotni tayyorlash va topshirish.
  

////////////////////////////////////////////////////////////////////////////////////////////////////////////////
NAZARIY MATERIALAR
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Funksiya o‘z – o‘zini chaqirishi deyiladi. U ikki xil – to‘g‘ri va bilvosita bo‘lishi mumkin. Agarda funksiya o‘zini o‘zi chaqirsa bu to‘g‘ri deyiladi. Agarda funksiya boshqa bir funksiyani chaqirsa va u funksiya o‘z navbatida birinchisini chaqirishi esa bilvosita deyiladi.
Ayrim muammolar yordamida osonroq yechiladi. Agarda ma’lumotlar ustida biror protsedura ishlatilsa va uning natijasi ustida ham xuddi shu protsedura bajarilsa, bunday hollarda ni ishlatish lozim. ikki xil natija bilan yakunlanadi: u yoki oxir – oqibat albatta tugaydi va biror natija qaytaradi, ikkinchisi hech qachon tugallanmaydi va xatolik qaytaradi.
Agarda funksiya o‘zini o‘zi chaqirsa, bu funksiyani nusxasi chaqirilishini aytib o‘tish lozim. yordamida yechiladigan muammo sifatida Fibonachchi qatorini ko‘rsatish mumkin.

1, 1, 2, 3, 5, 8, 13, 21, 34 …

Bu qatorning har bir soni (ikkinchisidan keyin) o‘zidan oldingi ikki sonning yig‘indisiga teng. Masala quyidagidan iborat: Fibonachchi qatorini 12 – a’zosi nechaga tengligini aniqlang. Bu muammoning yechishning usullaridan biri qatorni batafsil tahlil qilishdan iboratdir. Qatorning oldingi ikki soni birga teng. Har bir navbatdagi son oldingi ikkita sonning yig‘indisiga teng. YA’ni, o‘n yettinchi son o‘n oltinchi va o‘n beshinchi sonlar yig‘indisiga teng. Umumiy holda n – sonning yig‘indisi (n-2)- va (n-1) – sonlarning yig‘indisiga teng (n>2 hol uchun).
Rekursiv funksiyalar uchun ni to‘xtatish shartini berish zarur. Fibonachchi qatori uchun to‘xtatish sharti n<3 shartidir.
Bunda quyidagi algoritm qo‘llaniladi:

1. 
   Foydalanuvchidan Fibonachchi qatorining qaysi a’zosini hisoblashini ko‘rsatishini so‘raymiz.
   
2. 
   fib() funksiyasini chaqiramiz va unga foydalanuvchi tomonidan berilgan Fibonachchi qatori a’zosi tartib nomerini argument sifatida uzatamiz.
   
3. 
   fib() funksiyasi (n) argumentni tahlil qiladi. Agarda n<3 bo‘lsa, funksiya 1 qiymat qaytaradi; aks holda fib() funksiyasi o‘zini o‘zi chaqiradi va unga argument sifatida n–2 qiymatni beradi, keyin yana o‘z–o‘zini chaqiradi va bu funksiyaga n–1 ni qiymat sifatida beradi.
   
4. 
   Bundan keyin esa ularning yig‘indisini qiymat sifatida uzatadi.

   Agarda fib(1) funksiyasi chaqirilsa u 1 qiymatni qaytaradi. Agarda fib(2) funksiyasi chaqirilsa u ham 1 qiymatni qaytaradi. Agarda fib(3) funksiyasi chaqirilsa u fib(1) va fib(2) funksiyalarini yig‘indisini qaytaradi. fib(2) va fib(1) funksiyalari 1 qiymatni qaytarganligi sababli fib(3) funksiyasi qiymati 2 ga teng bo‘ladi.

   
   Agarda fib(4) funksiyasi chaqirilsa, bunda u fib(3) va fib(2) funksiyalari yig‘indisini qiymat sifatida qaytaradi. fib(3) funksiyasi 2 va fib(2) funksiyasi 1 qiymat qaytarishidan fib(4) funksiyasi 3 ni qiymat sifatida qaytarishi kelib chiqadi. Demak, Fibonachchi qatorining to‘rtinchi a’zosi 3 ga teng ekan.
   Yuqorida, tavsiflangan usul bu masalani yechishda unchalik samarali usul emas. fib(20) funksiyasi chaqirilsa, u tomonidan fib() funksiyasi 13529 marta chaqiriladi. Bunday hollarda ehtiyot bo‘lish lozim. Agarda Fibonachchi qatorining juda katta nomerini bersak xotira yetishmasligi mumkin. Fib() funksiyasini har safar chaqirilishida xotiradan ma’lum bir soha zahiralanadi. Funksiyadan qaytish bilan xotira bo‘shatiladi. Lekin, rekursiv tarzda funksiya chaqirilsa xotiradan uning uchun yangi joy ajratiladi va toki ichki funksiya o‘z ishini tugatmaguncha uni chaqirgan funksiya egallagan joy bo‘shatilmaydi. Shuning uchun xotirani yetishmay qolish xavfi bor. Fib() funksiyasining ishlatilishi 5.10. – listingda ko‘rsatilgan.
   Fibonachchi qatori a’zosining qiymatini topish uchun ni qo‘llanilishiga misol.

   #include

   
   int fib(int n);
   int main( )
   {
   int n, javob;
   cout << “Izlanayotgan nomerni kiriting:”;
   cin >> n;
   cout << “\n\n”;
   javob=fib(n);
   cout<< “Fibonachchi qatorining”<< n <<“nomeri qiymati ” <return 0;
   }
   int fib(int n)
   {
   cout << “fib(“<< n << “) jarayoni…”;
   if (n <3)
   {
   cout<< “1 qiymatni qaytarayapti!”\n;
   return (1);
   }
   else
   {
   cout<< “fib(” << n-2 << “) va fib(” <return(fib(n-2)+fib(n-1));
   }
   }
   NATIJA:
   Izlanayotgan nomerni kiriting:: 6
   fib(6) … fib(4) va fib(5) funktsiyalarini chaqirayapti.
   fib(4) … fib(2) va fib(3) funktsiyalarini chaqirayapti.
   fib(2) … 1 qiymatni qaytarayapti!
   fib(3) … fib(2) va fib(1) funktsiyalarini chaqirayapti.
   fib(1) … 1 qiymatni qaytarayapti!
   fib(2) … 1 qiymatni qaytarayapti
   fib(5) … fib(3) va fib(4) funktsiyalarini chaqirayapti.
   fib(3) … fib(2) va fib(1) funktsiyalarini chaqirayapti.
   fib(1) … 1 qiymatni qaytarayapti!
   fib(2) … 1 qiymatni qaytarayapti
   fib(4) … fib(2) va fib(3) funktsiyalarini chaqirayapti.
   fib(2) … 1 qiymatni qaytarayapti
   fib(3) … fib(2) va fib(1) funktsiyalarini chaqirayapti.
   fib(1) … 1 qiymatni qaytarayapti!
   fib(2) … 1 qiymatni qaytarayapti
   Fibonachchi qatorining 6 nomeri qiymati 8 ga teng
   
   
   

IZOH

Ayrim kompilyatorlar cout obyekti qatnashgan ifodalarda operatorlarni qullashda ba’zi qiyinchiliklar paydo bo‘ladi. Agarda kompilyator 28 satrdagi ifoda haqida ogohlantirish bersa ayirish operatsiyasini qavs ichiga oling, bu qator quyidagi ko‘rinishga ega bo‘lsin. 28: cout << “Call fib(“ <<(n-2)<<”) and fib(“ <<(n-2)<< “).\n”;

Funksiyaning ishlash tamoyili haqida .Funksiya chaqirilganda dastur boshqaruvi chaqirilgan funksiyaga uzatiladi, ya’ni funksiya tanasidagi operatorlarning bajarilishi boshlanadi. Funksiya operatorlari bajarilgach, u biror qiymatni natija sifatida qaytaradi (agarda u aniqlanmagan bo‘lsa funksiya void tipidagi qiymatni qaytaradi) va boshqaruv funksiya chaqirilgan joydan davom ettiriladi.

Bu masala qanday amalga oshiriladi? Dasturga uning boshqaruvi qaysi blokka o‘tishi lozimligi qanday ma’lum bo‘ladi? Argument sifatida aniqlangan o‘zgaruvchi qayerda saqlanadi? Funksiya tanasida aniqlangan o‘zgaruvchilar qayerda saqlanadi? Qaytariladigan qiymat qanday orqaga uzatiladi? Dasturga u qaysi joydan ish boshlashi kerakliligi qayerdan ma’lum?

Ko‘pgina adabiyotlarda bu savollarga javob berilmaydi. Lekin, funksiyani ishlash prinsipini bilmasak bizga kompilyatorning ishlash prinsipi juda mavhum bo‘lib ko‘rinadi. Shuning uchun ushbu mavzuda kompyuterning xotirasi bilan bog‘liq savollar ko‘rib chiqiladi.