Mavzu: Algoritmlarning matematika bilan bog’liqligi (8 soat) Reja

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:
void simpleIterativeReverse() {
char stack[80];
register int top = 0;
cin.getline(stack,80);
for (top = strlen(stack) - 1; top >= 0; cout.put(stack[top--]));
}