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

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).

• 1-Chiziqli rekursiya
• 2- Такрорланувчи рекурсия
• 3- Kaskadli (daraxtga o'xshash) rekursiya
• 4- кайтувчи(backtracking) рекурсия

• РЕКУРСИЯ ТУРЛАРИ

• 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)!