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

2. Cheklanmagan regestrli mashina

Hisoblash jarayonida ba’zi bir algoritmlarning o‘ziga qayta murojaat qilishga to‘g‘ri keladi. O‘ziga–o‘zi murojaat qiladigan algoritmlarga rekkurent algoritmlar yoki rekursiya deb ataladi. Biron bir masalani yechishda, agar uni bir xil kichik yoki sodda masalaraga bo’lib bajarish mumkin bo’lsa, bunday hollarda rekursiv algoritm qo’llash mumkin.

Hayotda uchrovchi ba’zi masalalarni hal etish rekursiv algoritmlarni qo’llash orqali oson va intutitiv tarzda kechadi. Misol sifatida Fibonachi sonlari ketma-ketligi, faktorial hisoblash va quyida rasmi keltirilgan “Hanoi minorasi” kabilarni keltirishimiz mumkin.
Rekursiya bu bir-biriga o’xshash hodisalarni ketma-ket, biroq avvalgisi ta’sirida biroz o’zgargan holda takrorlanishi yoki biror masalani yechishga shu tartibda yaqinlashish.
Afsonalarga ko’ra hind ibothonalaridan birida “Hanoi minora”si mavjud bo’lib uning uchta utruni va shu ustunlarga o’tkazilgan 64 ta tilla disklari bor. Ruhoniylar har kuni bir diksni ustunlarning biridan olib boshqasiga ko’chirishadi va ish bitishi taxminan 585 milliard yilni talab etadi. Disklarning o’lchami turli hil bo’lib ularni tartiblab bir ustunga qo’yilsa konus shaklini eslatadi. Maqsadlari oddiy, birinchi ustunda turgan bu disklarni oxir oqibat oxirgi uchunchi ustunga ko’chirish. Faqat qoida shuki: biror diskni ko’chirishda o’zidan kichigi ustiga qo’yish mumkun emas va doim eng yuqoridagi bitta diskni ko’chirish mumkun

Funksiya murojaatlari va rekursiya. Funksiyaga murojaat qilinganda nima sodir bo'ladi? Funksiya formal parametrlarga ega bo'lsa, amaldagi aktual parametrlar qimatlariga o'zgartirilishi lozim.Bundan taashqari, sistema programma yakuniy exe ijrosini qayerga saqlab davom ettirishi kerakligini bilishi kerak.Funksiyalar boshqa nom bilan, yoki asosiy dastur(the function main()) bilan ham chaqirilishi mumkin. Funksiyani qayerdan chaqirib olish, sistema tomonidan saqlab qolinshi kerak bo'ladi. Bu qaytish adreslarini asosiy xotirada saqlab borish orqali amalga oshirilishi mumkin, lekin bizga qancha joy kerakligi noma'lum bo'lsa, buning uchun ko'p ortiqcha joy ajratib ketish yaramaydi. Funksiyaga murojaatlarda esa adres qaytarishga qaraganda ko'proq ma'lumotlar saqlab qolinishi kerak. Shuning uchun, steklardan foydalanib dinamik joylashtirish yaxshi natijalarga olib keladi. Ammo, funksiyaga murojaatda qanday ma'lumotlar saqlanib qolishi kerak? Birinchidan, lokal o'zgaruvchilar to'planishi kerak.Agar x lokal o'zgaruvchisining e'loni mavjud bo'lgan f(1) funksiya, x o'zgaruvchini lokal e'lon qiluvchi f(2)funksiyaga murojaat qilsa, sistema bu ikki x o'zgaruvchilarni farqlay olishi kerak. Agar f2() x o'zgaruvchini ishlatsa, unda o'z x ini anglatadi; agar f2() x ga qiymat belgilasa, unda f(1) ga tegishli bo'lgan x o'zgarmasdan qoldirilishi kerak. Qachonki f(2) tugatilganda, f1()f(2)ga murojaat bo'linmasidan oldin xususiy x ga o'zlashtirilgan qiymatdan foydalanishi mumkin. Bu hozirgi ko'rilayotgan funksiya o'z-o'ziga rekursiv murojaat qilgandagi qismda, f(1) f(2)dek bir xil funksiya bo'lganda muhim. Sistema bu ikki x o'zgaruvchilarni qanday farqlaydi? main() ni o'z ichiga oluvchi har bir funksiyaning holati ularning tarkibidagi barcha lokal o'zgaruvchilar, funksiya parametrlarining qiymatlari va funksiyaga murojaat qayerdan boshlanishi kerakligini ko'rsatuvchi adres indikatorlari orqali harakterlanadi.Barcha shu ma'lumotlarni o'zida saqlovchi ma'lumotlar maydoni aktivatsiya hisoboti (activation record) yoki stek(kompyuterning ma'lumotlar to'planadigan sistemasi) ramkasi (stack frame) deb ataladi va stek(kompyuterning ma'lumotlar to'planadigan joyi)da saqlanadi. Aktivatsiya hisoboti ancha vaqtgacha funksiya o'zining amal doirasini yo'qotmagan holda saqlanadi. Bu hisobot – funksiyaning xususiy umumiy birlashtirilgan ma'lumotlar joyi bo'lib, unda dasturlarning yaxshi ishga tushishi uchun zarur bo'lgan barcha ma'lumotlar saqlanadi. Aktivatsiya ma'lumotlari odatda ko'p saqlanmaydi, chunki ular funksiya ishga tushirilganda dinamik joylashadi va funksiyadan chiqilganda joylashuvidan chetlashadi. Faqatgina main() funksiyasidagi ma'lumotlar ancha vaqt saqlanadi.
Odatda aktivatsiya hisoboti(rekordi) quyidagi ma'lumotlarni o'zida saqlaydi:
■ Funksiyaning barcha parametrlari uchun qiymatlar, massiv yacheykalari joylashgan manzillarni va o’zgaruvchilarni saqlaydi va barcha boshqa ma’lumotlar bandlaridan nusxa oladi.
■ Har qaysi holda, har qayerda saqlanishi mumkin bo’lgan lokal o’zgaruvchilarningqayerda saqlanishini ko’rsatuvchi deskriptor va ko’rsatkichlarinigina saqlaydi.
■ Murojaat etuvchining adresini va joriy murojaatlar holatini nazorat qiladi.
■ Murojaat ko’rsatkichlarining dinamik aloqasini ta’minlab turadi.
■ Funksiya qaytargan qiymat void sifatida e’lon qilinmaydi. Chunki, aktivatsiya jarayoni hajmi bir murojaatdan boshqasiga farq qilishi mumkin, qaytarilgan qiymat murojaat aktivatsiyasining o’ng tomonida joylashadi.
Zikr etilganidek, agar funksiya main() yoki boshqa funksiya orqali atalgan bo’lsada, uning aktivatsiya rekordi ishga tushirish vaqti steki(run-time stack)da yaratiladi. Stek doimo funksiyaning joriy holatiga ta’sir etadi. Misol uchun, main() f1()ni, f1() f2()ni, f2() esa o’z navbatida f3()ni chaqiradi deb tasavvur qiling. Agar f3() ishga tushirilayotgan paytdagiishga tushirish vaqti steki 5.1 chizmada ko’rsatilgan. Stek xususiyatiga ko’ra, agar f3() uchun faollashtirish rekordi f3()ning qaytaruvchi qiymatining yonida stek ko’rsatkichini o’zgartirish orqali darhol surilsa, keyin f2() ijrosi amalga oshirilsa va hozirda ma’lumotlar xususiy ombori uning ijrosini qayta aktivlashtirish uchun muhim bo’lgan bepul kirishga ruxsat bor. Boshqa tomondan, agar f3() boshqa f4() funksiyani chaqirsa, keyin ishga tushirish vaqti steki o’zining yuqorligini orttiradi, chunki f4() uchun faollashtirish rekordi stekda amalga oshiriladi va f3()ning faolligi to’xtatiladi.
3.1-rasm. Ishga tushirish vaqti stekining main() f1()ni , f1() f2()ni, f2() f3() ni chaqirgandagi tarkibiy qismlari:

Aktivatsiya, ya’ni faollik rekordini yaratish funksiyaga murojaat qilinganda sistemaga rekursiyani o’z holatida saqlab turiwiga ruxsat beriladi. Qachonki bir xildagi murojaat mavjud bo’lganda rekursiya funksiyaga murojaat qiladi. Shuning uchun, rekursiv murojaat funksiyaning o’ziga murojaat degani emas, balki bir xilda uchrashi mumkin bo’lgan funksiyalarga murojaat. Bular har xil faollik rekordlarida namoyon bo’ladi va sistema ularni farqlab oladi.