Mavzu:
Rekursiya va uni dasturlashda ishlatish. Rekursiv algoritmlar,
ularning tahlili.
REJA:
1. Rekursiyaga doir misollar. Daraxtsimon maʻlumotlar tuzilmalari.
2. Taʻriflar va xususiyatlar. Daraxtlar klassifikatsiyasi. Daraxt ko‘ruvi.
3. Ikkilik daraxtlar va ular ustida amallar.
Rekursiv algoritm f dasturlash tilida yozilgan. Rekursiya va rekursiv algoritmlar.
Asosiy ta'riflar. Daraxtlarni tasvirlash usullari Rekursiya - bu subroutin o'zini o'zi
chaqiradigan vaziyat. Bunday algoritmik qurilishga birinchi marta duch kelganda,
ko'pchilik muayyan qiyinchiliklarga duch keladi, ammo ozgina amaliyot va
rekursiya
sizning dasturiy arsenalingizda tushunarli va juda foydali vositaga aylanadi. 1.
Rekursiya mohiyati Protsedura yoki funktsiya boshqa protseduralar yoki
funktsiyalarni chaqirishni o'z ichiga olishi mumkin. Protsedurani o'z ichiga olishi
mumkin. Bu erda hech qanday paradoks yo'q - kompyuter faqat dasturda uchragan
buyruqlarni ketma-ket bajaradi va agar u protsedura qo'ng'irog'iga duch kelsa,
shunchaki ushbu protsedurani bajarishni boshlaydi. Buni qanday buyruq berganligi
muhim emas. Rekursiv protseduraga misol: Rec (a: butun) protsedurasi; agar
boshlang\u003e
a Agar asosiy dasturda, masalan, Rec (3) shaklida qo'ng'iroq qilinsa
nima bo'lishini ko'rib chiqing. Quyida bayonlarning ketma-ketligini ko'rsatuvchi
jadval. Anjir. 1. Rekursiv protseduraning blok diagrammasi. Rec protsedurasi a
\u003d 3. parametri bilan chaqiriladi, unda a \u003d 2 parametrli Rec protsedurasiga
qo'ng'iroq bor. Oldingi qo'ng'iroq hali tugallanmagan, shuning uchun siz boshqa
protsedura yaratilayotganligini tasavvur qilishingiz mumkin va uning ishi oxiriga
qadar u o'zining birinchi ishini tugatmaydi. A \u003d 0 parametridan so'ng qo'ng'iroq
jarayoni tugaydi. Ayni paytda protseduraning 4 ta nusxasi bir vaqtning o'zida
bajariladi. Bir vaqtning o'zida
bajariladigan protseduralar soni chaqiriladi rekursiya chuqurligi. (Rec
(0)) deb
nomlangan to'rtinchi protsedura 0 raqamini bosib chiqaradi va o'z ishini
yakunlaydi. Shundan so'ng, boshqaruv uni (Rec (1)) deb nomlangan protseduraga
qaytadi va 1-raqam bosiladi va hokazo, barcha protseduralar tugaguncha. Dastlabki
qo'ng'iroq natijasi to'rtta raqamni chop etadi: 0, 1, 2, 3. Nima bo'layotganining yana
bir vizual tasviri sek. 2. Anjir. 2. Rec protsedurasini 3-parametr bilan bajarish, 2-
parametr bilan Rec protsedurasini bajarish va 3-raqamni bosib chiqarish, o'z
navbatida, 2-parametr bilan Rec protsedurasini bajarish, 1-parametr bilan Rec
protsedurasini bajarish va 2-raqamni bosib chiqarish va boshqalarni o'z ichiga oladi.
Mustaqil mashq sifatida Rec (4) ni chaqirganda nima bo'lishini o'ylang. Shuningdek,
quyida tasvirlangan Rec2 (4) protsedurasini chaqirganda nima yuz berishi haqida
o'ylang, bu erda operatorlar almashadi. Rec2 protsedurasi (a: butun); writeln (a)
boshlash; agar a\u003e 0 bo'lsa, Rec2 (a-1); oxiri; Yuqoridagi misollarda
rekursiv
chaqiruv shartli gapning ichida ekanligini unutmang. Bu rekursiyani to oxirigacha
davom ettirish uchun zarur shartdir. Shuni ham yodda tutingki, protseduraning o'zi
boshqa parametr bilan chaqiriladi, lekin u chaqirilgandek emas. Agar protsedura
global o'zgaruvchilardan foydalanmasa, unda rekursiya
cheksiz davom etmasligi
kerak. Bir oz murakkabroq sxema mumkin: A funktsiyasi B funktsiyasini chaqiradi va
o'z navbatida A ni chaqiradi murakkab rekursiya. Bunday holda, birinchi bo'lib
tasvirlangan protsedura hali tavsiflanmagan bo'lishi kerak. Buni amalga oshirish
uchun foydalanish kerak. Jarayon A (n: butun son); (Birinchi protseduraning avans
tavsifi (nomi)) B protsedurasi (n: butun son); (Ikkinchi protseduraning avans tavsifi)
A (n: butun son) protsedurasi; (Protseduraning to'liq tavsifi A) writeln (n) boshlanadi;
B (n-1); oxiri; protsedura B (n: butun son); (B protseduraning to'liq tavsifi) boshlanadi
wr (n); agar n B protsedurasining batafsil tavsifi sizga
uni A protsedurasidan
chaqirishga imkon beradi. Ushbu misolda A protsedurasining batafsil tavsifi talab
qilinmaydi va estetik sabablarga ko'ra qo'shiladi. Agar oddiy rekursiyani bizning
oboborosga o'xshatish mumkin bo'lsa (3-rasm), unda murakkab recursion tasvirini
“Qo'rquvdan bo'rilar bir-birini eb yuborgan” mashhur bolalar she'ridan yig'ish
mumkin. Ikki bo'rining bir-birini eyishini tasavvur qiling, shunda siz murakkab
rekursiyani tushunasiz. Anjir. 3. Ouroboros - dumini yutib yuboradigan ilon. Teodor
Pelekanosning (1478) "Sinosius" kimyoviy traktatidan olingan rasm. Anjir. 4.
Murakkab rekursiya. 3. Rekursion yordamida ko'chadan simulyatsiya qilish Agar
protsedura o'zini o'zi chaqirsa, demak, mohiyatan, bu tsiklning ishlashiga o'xshash
tarkibiy ko'rsatmalarning takroriy bajarilishiga olib keladi. Ba'zi dasturlash tillarida
umuman tsiklli konstruktsiyalar
mavjud emas, bu esa dasturchilarni takrorlash
yordamida takrorlashni tashkil qilish uchun qoldiradi (masalan, Prolog, bu erda
rekursiya asosiy dasturlash uslubidir). Masalan, for loopning ishini taqlid qiling.
Buning uchun, masalan, protsedura parametri sifatida bajarilishi mumkin bo'lgan
o'zgaruvchan qadam hisoblagichiga ehtiyoj bor. 1-misol LoopImitatsiya protsedurasi
(i, n: butun son); (Birinchi parametr - qadam hisoblagichi, ikkinchi parametr - bu
qadamlarning umumiy soni) writeln boshlanadi
("Salom N", i); // Mana, agar i takrorlansa,
ko'rsatmalar mavjud LoopImitatsiya turini (1, 10) chaqirish natijasida, hisoblagichlar
1 dan 10 gacha o'zgargan holda ko'rsatmalarning o'n barobar bajarilishi bo'ladi, bu
holda u bosadi: Salom N 1 Salom N 2 … Salom N 10 Umuman olganda, protsedura
parametrlari hisoblagich qiymatlarining o'zgarishi chegarasi ekanligini ko'rish qiyin
emas. Quyidagi misolda bo'lgani kabi, siz takrorlanadigan qo'ng'iroqni va
takrorlanadigan ko'rsatmalarni almashtirishingiz mumkin. 2-misol LoopImitation2
protsedurasi (i, n: butun son); agar
i Bunday holda, ko'rsatmalar bajarilishidan oldin,
protseduraga rekursiv qo'ng'iroq paydo bo'ladi. Hisoblagichning maksimal qiymatiga
erishmagunimizcha protseduraning yangi namunasi, avvalambor, boshqa misolni
chaqiradi va hokazo.
