Dasturlash I 12-hafta mavzu: Rekursiv funksiyalar

DASTURLASH I


12-HAFTA


Mavzu: Rekursiv funksiyalar

Hafta	Mavzu	Mashg‘ulot turi	Soat	Mashg‘ulot mazmuni
14-haf-ta	Funksiyalar	14-Ma’ruza	2	Rekursiv funksiyalar, to‘g‘ridan-to‘g‘ri va qiyosiy rekursiya.
		Lab_14.1	2	Rekursiv funksiyalardan foydalanib oddiy dasturlar tuzish.
		Lab_14.2	2	To‘g‘ridan-to‘g‘ri va qiyosiy rekursiyaga doir dasturlar tuzish.
		Lab_14.3	2	Tuzilgan dasturni avtomatik tarzda onlayn tekshiruvchi dastur yordamida nazorat ishini topshirish.
		14-Mustaqil ish	2	Topshiriqda berilgan savollarga javob yozish
			1	Test savollariga javob berish
			5	Dastur tuzishga doir topshiriqlarni bajarish.

14-MA’RUZA
MAVZU: REKURSIV FUNKSIYALAR, TO‘G‘RIDAN-TO‘G‘RI VA QIYOSIY REKURSIYA.

Reja:

1. 
   Rekursiya tushunchasi;
   
2. 
   Misol: Faktoriallar;
   
3. 
   Amaliy qism: Fibonachichi;
   
4. 
   Rekursiyadan foydalanib masalani yechish;
   
5. 
   Rekursiv yordamchi funksiyalar;
   
6. 
   Xanoy minoralari;
   
7. 
   Sakkiz qirolicha;
   
8. 
   Quyi rekursiya.
   

Kalit so‘zlar:

• 
  base case
  
• 
  infinite recursion
  
• 
  recursive function
  
• 
  recursive helper function
  
• 
  stopping condition
  
• 
  tail recursion
  

14.1. Rekursiya tushunchasi
Kalit Point. Rekursiya – oddiy sikl yordamida dasturlash mushkul bo`lgan masalalarni oqilona hisoblash usulidir.
Faraz qilaylik, satrning belgilarini mumkin bo`lgan barcha kombinatsiyalarda chop etuvchi dastur tuzishimiz kerak. Masalan, abc belgilariga ega satrni abc, acb, bac, bca, cab va cba ko`rinishlarida chop etuvchi dastur. Xo`sh, bu masalaning qanday yechimi bor? Buning bir nechta yo`llari mavjud. Bu kabi masalalarni yechishning oqilona va samarali usuli – rekursiyadan foydalanishdir.
14.1-rasmda tasvirlangan, klassik Sakkiz qirolicha boshqotirmasi qoidasiga ko`ra, shaxmat doskasiga sakkizta qirolicha, bir-biriga xavf tug`dirmaydigan holda (ya’ni, ikkita qirolicha bitta satrda, bitta ustunda yoki bitta diagonalda bo`lmasligi lozim) joylashtiriladi. Bu masalani yechuvchi dastur qanday yoziladi? Bu muammoni hal qilishning bir necha usullari mavjud. Ammo, ular ichida, bunday vaziyatlar uchun eng maqbuli – rekursiyadan foydalanishdir.

14.1-rasm. Sakkiz qirolicha masalasini rekursiya yordamida yechish mumkin.
Rekursiyadan foydalanish – bu o`z-o`zini chaqiruvchi funksiyalardan foydalanib dasturlash demakdir. Rekursiya – dasturlashning foydali usuli. Ba'zi hollarda, bu bizga boshqa murakkab muammolarga tabiiy, sodda, oddiy yechimlar asosida yondoshish imkonini beradi. Keyingi qismlarda rekursiv dasturlash tushunchalari va usullari namunaviy misollar asosida bajafsil yoritilgan.