Rekursiya haqida tushuncha. Funksiya murojaatlari va rekursiya joriyi Rekursiv algoritm va uning turlari

Funksiya murojaatlari va rekursiya joriyi. 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.