Ma’lumotlar tuzilmasi va algoritmlar

Chizma 5.2 Power(5.6,2) darajasining ijrosi vaqtida ishga tushirish vaqt stekidagi o’zgarishlar.



Bu jarayon bir pasda amalga oshmaydi. Chunki, Sistema power(5.6,1)ning qiymatini bilmaydi; avval bu hisoblanishi kerak. Shuning uchun, power()ga 5.6 va 1 argumentlari orqali qayta murojaat qilinadi. Ammo, bu murojaat amalga oshirmasidan avval, ishga tushirish vaqt steki yangi belgilarni qabul qiladi, bu 5.2b chizmada ko’rsatilgan. Va 2-argument 0 yoki 0 emasligi tekshiriladi. Bu 1 ga tengligi sabab, power() 3-marotaba chaqiriladi, bu safar 5.6 va 1 argumentlari bilan. Funksiya ijrosidan keyin, Sistema argumentlarni eslab qoladi va ularni steklarga jpylab adreslarni eslab qoladi, 1 ta yacheykani natija uchun saqlab qo’yadi. Chizma 5.2c da ham shu jarayonlar davomini ko’rishingiz mumkin. Natija saqlanadigan stek yacheykasi adawib ketmasligi muhim. SP har bosqichda oshib boradi.
Endi power()ga 2-murojaat yakunlanishi mumkin, chunki bu power(5.6; 1) ning natijasini kutgan edi. Bu natija, 1.0 , 5.6ga ko’paytiriladi va natija maydonida saqlanadi. Chizma 5.2f SP ning qiymati o’zgarmasdan oldingi stekning holatini ko’rsatadi va chizma 5.2g stekning bu o’zgarishdan keyingi holatini ko’rsatadi. Shu o’rinda, power() 1-murojaat natijasini 2-murojaat natijasiga ko’paytirib tugallashi mumkin, 1-argumenti orqali yana 5.6. Va y ga o’zlashtiriladigan natijaviy qiymat 31.36. Bundan oldingi stek holati Chizma 5.2h dagidek bo’ladi. Power() funksiyasi hech qanday rekursiyasiz quyidagicha boshqacha bajarilishi ham mumkin::
double nonRecPower(double x, unsigned int n) { doubleresult=1;
for(result=x;n>1; --n) result *=x;
returnresult;
}


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