Rekursiv ma’lumotlar tuzilmasi. Rekursiv 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;

}