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

Rekusiv murojaat anatomiyasi
Ixtiyoriy o’suvchi x ning manfiy bo’lmagan butun n-darajasini aniqlovchi funksiya rekursiv funksiyaga misol bo’ladi. Uni aniqlovchi funksiya quyidagicha:

X ning n-darajasini hisoblovchi funksiya C++da quyidagi pow orqali to’g’ridan – to’g’ri hisoblanishi mumkin:

Bundan foydalanib, xning 4-darajasining qiymati quyidagicha yo’nalishda hisoblanishi mumkin:
Bunday ketma-ketlik rekursiv murojaatlar zanjirining so’nggi bosqichiga, ya’ni ildiziga olib boradi. Ildiz natijaga daraja 0 bo’lganda 1 qiymatni beradi; natija undan oldingi murojaatlarga o’tqaziladi. Ijrosi amalga oshayotgan murojaat x*1=x degan natija beradi. Keyin, bu raqam ikkinchi murojaaat uchun x*x orqali shunaqa natijani qaytaradi. So’ng, x * x * x natijasiga olib keladi.
call 1 x 4 = x · x 3 = x · x · x · x
call 2 x · x 2 = x · x · x
call 3 x · x 1 = x · x
call 4 x · x 0 = x · 1 = x
call 5 1or alternatively, as
call 1 power(x,4)
call 2 power(x,3)
call 3 power(x,2)
call 4 power(x,1)
call 5 power(x,0)
call 5 1
call 4 x
call 3 x · x
call 2 x · x · x
call 1 x · x · x · x
Funksiyalar ijrosi amalga oshayotganda sitema nima ish bajaradi? Barchamizga ma’lumki, Sistema amalga oshirish vaqti stekida barcha murojaatlar izlarini saqlab turadi.Funksiya ijrosidan so’ng ijro exe si qayerda saqlanganligini bilish uchun zarur. Buning uchun misol qilib , 102 yoki 105 raqamalari kiritilgandagi power() funksiyasi bir chiziqda yoadigan bo’lsin.

Rekursiv murojaatlar izi bu diagrammada ko’rsatilganidek oddiy.
call 1 power(5.6,2)
call 2 power(5.6,1)
call 3 power(5.6,0)
call 3 1
call 2 5.6
call 1 31.36
Chunki, ko’pgina operatsiyalar amalga oshirish vaqti stekida amalga oshirilgan. Funksiya 1 – marotaba ishga tushirilganda, 4 ta belgi amalga oshirish vaqti stekida suriladi: qaytuvchi adres 136, aktual parametrlar 5.6 va 2, va 1 ta power() orqali qaytarilgan qiymat uchun joyni aniqlovchi ishga tushadi. 5.2a chizma shu holatni namoyon etadi. (shunda va boshqa diagrammalarda, SP - stack pointer, AR - activation record, va so’roq belgilari qaytarilgan qiymatlar joyini aniqlahga xizmat qiladi. ) Hozir power() (daraja()) funksiyasi amalga oshirilgan.
3.2-rasm. 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 3.2b rasmda 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. 5.2c rasmda 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. 3.2f-rasm SP ning qiymati o’zgarmasdan oldingi stekning holatini ko’rsatadi va 3.2g-rasm 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 3.2h-rasmdagidek 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;
}