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:
Rekursiya tushunchasi;
Misol: Faktoriallar;
Amaliy qism: Fibonachichi;
Rekursiyadan foydalanib masalani yechish;
Rekursiv yordamchi funksiyalar;
Xanoy minoralari;
Sakkiz qirolicha;
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.
Do'stlaringiz bilan baham: |