“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

Rekursiv ob’ektlarga misollar.

Ta’rif .Agar ma’lumotlar tuzilmasi elementlari ham mazkur tuzilmaga o’xshash tuzilma bo’lsa , u holda bunday tuzilmaga rekursiv ma’lumotlar tuzilmasi deyiladi. Rekursiv funksiyani ishlatish uchun :

• Rekursiv masala umuman olganda bir nechta bosqichlarga bo’linadi.
• Uni echish uchun rekursiv funksiya chaqiriladi.
• Rekursiv funksiya masalaning eng sodda (yani bazaviy ) qismini echa oladi.
• Agar bu funksiya bazaviy masalani echish uchun chaqirilsa, u natijani qaytaradi.
• Agar bu funksiya murakkabroq masalani echish uchun chaqirilsa,u masalani 2ga ajratadi:1-qism – u echa oladigan masala (bazaviy ); 2-qism –echa olmaydigan, lekin dastlabki masalaga o’xshash va undan osonroq,kichikroq bo’lgan masala

Ushbu yangi masala boshlang’ich masalaga o’xshash bo’lgani uchun funksiya o’zining yangi kopiyasini chaqiradi – bu rekursiv chaqiruv yoki rekursiya qadami deyiladi.

• Ushbu yangi masala boshlang’ich masalaga o’xshash bo’lgani uchun funksiya o’zining yangi kopiyasini chaqiradi – bu rekursiv chaqiruv yoki rekursiya qadami deyiladi.
• Rekursiya qadami return kalit so’zini o’z ichiga olishi kerak.
• Rekursiya qadami funksiyaga dastlabki murojaat yopilmaguncha bajariladi.
• Rekursiya jarayonini tugatish uchun funksiya har gal o’zini sal soddaroq masala uchun chaqirganda bazaviy masalaga intiluvchi, kichiklashib boruvchi masalalar ketma-ketligi shakllanishi kerak. Funksiya bazaviy masalaga etib boradi va uni echadi, va natijasini qaytaradi va x.k.
• Shunday qilib,endi qaytarish ketma-ketligi dastlabki murojaatgacha ishlaydi va oxirgi natijani qaytaradi(qaerdan murojaat bo’lgan bo’lsa).

Rekursiv triada.

• Parametrizatsiya qilish – masala shartini tasniflash va uni hal etish uchun parametrlar aniqlanadi;
• Rekursiya bazasi (asosi) – masala yechimi aniq bo’lgan trivial holat aniqlanadi, ya’ni bu holatda funksiyani o’ziga murojaat qilishi talab etilmaydi.;
• Dekompozitsiya – umumiy holatni nisbatan ancha oddiy bo’lgan o’zgaruvchan parametrli qism masalalar orqali ifodalaydi.

Izoh
Rekursiv yoki interatsion usul samaradorligi berilgan masalani hal qiluvchi dasturni turli boshlang’ich qiymatlarda tahlil etish orqali aniqlanadi.
Izoh
Rekursiv algoritmlarni samaradorligini oshirish ko’pincha triada bosqichlarini qayta ko’rib chiqish natijasida amalga oshirish mumkin.