Рекурсив маълумотлар тузилмаси

• 9-Mavzu (3-davomi): Rekursiya va ularni dasturlashda ishlatish

Rekursiya haqida tushuncha.

• Rekursiya (umuman) – bu ob’ektni mazkur ob’ektga murojaat qilish orqali aniqlashdir

• Rekursiv (funksiya) algoritm – bu shu funksiyani (algoritmni) aniqlashda o’ziga bevosita yoki bilvosita (boshqa funksiyalar orqali) murojaat qilishdir.

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.

• Misol. Faktorialni hisoblash
• n!=1*2*…*n=n*(n-1)!
• int i,m,N; double long fact;
• void factorial(int m);
• void main()
• { clrscr();
• cin>>N;
• fact=1;
• factorial(N);
• }
• void factorial(int m)
• {
• if( (m==1) || (m==0)){
• cout<
• getch();
• exit (1);
• }
• fact*=m;
• factorial(m-1);
• }

• Rekursiv triada:
• Parametrizatsiya:
• n – номанфий бутун сон.
• Rekursiya bazasi:
• n =0 ва n =1 учун факториал 1 га тенг.
• Dekompozitsiya:
• n!= n *(n-1)!