|
Dumli rekursiya. Barcha rekursiyalar uchun aniqlanayotgan to’plam yoki funksiyaning ma’lumotlari o’zida jamlanishi kerak. Bunaqa ma’lumotlarning juda ko’p turlari joriy etilishi mumkin. Bu ma’lumotlardan ko’p marotaba, turli yo’sinlarda foydalanish mumkin. Rekursiyaning turli darajalari mavjud bo’lib, ularning murakkablik darajalari ham turlicha. Quyida, bunday turlarning ba’zilari muhokama qilinadi. Ularning oddiysi – dumli rekursiya. Dumli rekursiya faqatgina bitta rekursiv murojaatni funksiya oxirida qo’llash orqali harakterlanadi.Boshqacha qilib aytganda, murojaat bo’lganda, funksiya orqali amalga oshirilishi kerak bo’lgan birorta so’z qolmaydi; rekursiv murojaat eng so’nggi emas, unda erta bo’lmagan, to’g’ridan-to’g’ri yoki o’zlashtirma turdagilari ham mavjud. Misol uchun, tail() funksiyasi quyidagicha aniqlanadi:
void tail(int i){
if(i>0){cout<
tail(i-1);}
}
tail (dumli ) rekursiya li funksiyaga misol, bundaki nonTail funksiyasi quyidagicha izohlanadi:
void nonTail(int i) {
if (i > 0) {
nonTail(i-1);
cout << i << '';
nonTail(i-1);
}
}
Dumli rekursiya qurilishi oddiygina va kimdir tomonidan osonlikcha joylashtirilishi mumkin. Buni quyidagi I o’zgaruvchining qiymatini unga bo’lgan rekursiv murojaatlar darajasi orqali kamaytirib borish misolida ko’rish mumkin. Bunda, tail() iterativ funksiya orqali ifodalanishi mumkin:
void iterativeEquivalentOfTail(int i) {
for ( ; i > 0; i--)
cout << i << '';
}
Dumli rekursiyani iteratsiya orqali foydalanishning afzalligi mavjudmi? C++ kabi tillar uchun, solishtiriladigan hech qanday foydali tomonlari bo’lmasligi mumkin, lekin Prolog kabi tillarda bu juda kata ahamiyatga ega bo’ladi. If goto bilan birga qo’llaniladigan hollarda dumli rekursiyadan foydalanmaslik ma’qul.
Dumsiz rekursiya. Rekursiyalarda mavjud boshqa muammo bu qiymat kiritish qatorlarini teskari tartibda chiqarib berishdir. Quyida oddiy rekursiya qo’llanilishi berilgan:
/* 200 */ void reverse() {
char ch;
/* 201 */ cin.get(ch);
/* 202 */ if (ch != '\n') {
/* 203 */ reverse();
/* 204 */ cout.put(ch);
}
}
Aldab qo’yadigan joyi qayerda? Bu funksiya nimadir bajaradigandek tuyulmaydi hech. Lekin bu rekursiyaning ahamiyatliligi bilan main() ning reverse() ko’rinishidagi turi va kiritish “ABC” qatordir. Avvalo, buni faollashtirish yacheykalar orqali ch o’zgaruvchi uchun amalga oshiriladi va adresni qaytaradi. Funksiya nomi yonida void ishlatilsa funksiya hech qanaqa qiymat qaytarmaydi, shuning uchun, natija yacheykasi uchun ham hech qanaqa almashtirishlar kerak emas. get() funksiyasi birinchi belgida “A” ni o’qiydi. Chizma 5.3a birinchi marotaba reverse() o’z-o’ziga murojaat qilgandagi ishga tushirish vaqt stekidagi holat ko’rsatilgan.
3.3-rasm. reverse() amalga oshirilgandagi ishga tushirish vaqt stekidagi o’zgarishlar.
Ikkinchi belgi o’qib olindi va so’nggi belgi ekanligiga tekshiriladi va unday bo’lmasa reverse()ga qayta murojaat qilinadi. Lekin har qanaqa holatda ham , ch ning qiymati qaytarilgan qiymat bo’yicha ishga tushirish vaqti stekga joylashtiriladi. Reverse 3-marotaba chqirilmasidan oldin, stekda ikki yoki undan ortiq belgilar mavjud(3.3b -rasm) So’nggi belgiga yetmaguncha funksiyaga qayta-qayta murojaatlar bo’laveradi. Bizning misolimizda, reverse()ga 4 marta murojaat etilgan va so’nggi murojaatgacha bo’lgan o’zgarishlar va jarayonlar 3.3d da ko’rsatilgan. To’rtinchi murojaatda, get() so’nggi belgini topadi va reverse() boshqa ishlamaydi. Sistema faollashtirish natijalaridan uning adresii qaytaradi va SPni orttirish orqali aniq bitlar yordamida bu rekordni yaroqsiz qilib tashlab yuboradi. Bajarilgan amallarni chop etish uchun 204 qatordan boshlanadi.Uchinchi murojaat faollik rekordi faol bo’lganda, ch ning qiymati, “C” harfi, birinchi belgi sifatida ekranga chiqariladi. Va nihoyat, reverse() ning birinchi murojaatining faollik rekordiga yetib kelindi. Keyin “A” chiqariladi va ekranda ko’rilishi mumkin bo’lgan qator “CBA” ko’rinishida bo’ladi. Birinchi murojaat butunlay yakunlanadi va dastur ijrosi main() da bo’ladi.
Bir xil funksiya uchun rekursiv hamda rekursiv bo’lmagan ijrolarini taqqoslang:
Do'stlaringiz bilan baham: |
