Rekursiv triada
Masalalarni rekursiv usulda yechish uchun rekursiv triada deb ataluvchi quyidagi bosqichlar ishlab chiqiladi::
Parametrlarni aniqlash – masalaning shartlarini tavsiflash uchun va yechimni olishda qo’llaniladigan parametrlarni tanlash;
Rekursiya tayanchi (bazisi) – yechimni olish vaqtida funktsiyaning o’ziga murojaatni talab etmaydigan arzimas holatlarni aniqlash;
dekompozitsiya – umumiy masalani parametrlarni o’zgartirish orqali ancha sodda qism masalalarga ajratgan holda ifodalash.
39. Rekursiv ob’ektlarga misollar keltiring?
Bizni o’rab turgan dunyoda o’z-o’ziga o’xshash ob’ektlardan tashkil topgan buyumlarni uchratamiz. Ya’ni katta ob’ektining qismlari aynan ushbu ob’ektning o’zidan iborat bo’ladi. Bunday ob’ektlar reskursiv deyiladi
Masalan, daraxtning bargi aynan daraxtning shoxlanishiga o’xshash tasvirni taqdim etadi.
Tashqaridan qaragandan rekursiya yetarli darajada juda oddiy va maxsus bilimlarni talab chilmaydigandek ko’rinadi.
Rekursiv ob’ektlarga misol sifatida quyidagi grafik tasvirlarni olish mumkin. Bunda tasvirlar o’z-o’zini takrorlovchi, bitta ob’ekt sifatida qaraladi.
40. Rekursiv Bezu koeffitsientlari haqidagi masalani yechish uchun rekursiv triada ishlab chiqing?
Ixtiyoriy n va m natural sonlar uchun Bezu koeffitsientlarini toping, ya’ni bu koeffitsientlar shunday a va b butun sonlar bo’lishi kerakki, EKUB(n,m)=a*n+b*m (bu yerda EKUB(n,m) –n va m butun sonlarning eng katta umumiy bo’luvchisi).
Parametrlarni aniqlash. m, n – berilgan natural sonlar, o’zgarmas parametrlar; d – berilgan sonlarning umumiy bo’luvchisi, o’zgarmas parametr; bm, bn – mos ravishda n va m lar uchun Bezu koeffitsientlari, bu parametrlar rekursiv tarzda funktsiyani navbatdagi chaqirishda o’zgaradi.
Rekursiya tayanchi. Agar berilgan parametrlar bilan funktsiyani navbatdagi chaqirishda d=m*bm–n*bn tenglik bajarilsa, u holda Bezu koeffitsientlari topilgan bo’ladi. Chiziqli kombinatsiya talab qilinadi.
Dekompozitsiya. Agar tenglik bajarilmasa, u holda (n yoki m) sonlardan kichik koeffitsientlarni inkrement ravishda oshirib boring. Rekusiv funktsiya keyingi chaqirishda alohida parametrlar to’plamining o’zgarishi bilan bajariladi. Buning uchun rekursiya tayanchi qayta tekshiriladi va rekursiv algoritm qayta takrorlanadi (yoki tayanchga erishiladi va funktsiya ishi yakunlanadi, yoki dekompozitsiyali o’tishlar bajariladi).
