Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti urganch filiali kompyuter injineringi fakulteti

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA
KOMMUNIKATSIYALARINI RIVOJLANTIRISH
VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT
AXBOROT TEXNOLOGIYALARI UNIVERSITETI
URGANCH FILIALI KOMPYUTER INJINERINGI FAKULTETI
961-20 GURUH TALABASI BEKCHANOV MUNISNING

Mustaqil ishi


Topshirdi: _______________
Qabul qildi: _______________


Urganch-2022 yil.
Mavzu: Rekursiya haqida tushuncha.
Reja:

1. 
   Funksiya murojaatlari va rekursiya joriyi
   
2. 
   Rekursiv algoritm va uning turlari
   

Dinamik ma’lumotlar tuzilmasi. Bizga ma’lumki, massivlar (static tuzilmalar) dasturlash tillarida juda foydali va zaruriy tuzilmadir. Lekin uning ikkita kamchiligi bor.Uning o’lchamini dasturbajarilishi mobaynida o’zgartirib bo’lmaydi.Tuzilma orasiga element kiritish uchun qolganlarini surish kerak.Bu kamchilik bog’langan ro’yhatlar bilan ishlashga olib keladi. Bog’langan ro’yhatlar bir xil toifadagi elementlar (tugunlar) ketma-ketligi bo’lib, ular xotirada turli joylarga joylashtiriladi va o’zaro bir-biri bilan ko’rsatkichli maydonlar orqali bog’lanadi. Bog’langan ro’yhatlarni dasturda turlicha amalga oshirish mumkn.Bog’langan ro’yhatlarda elementlarni quyidagicha xosil qilib olamiz:

Informatsion ko’rsatkichli
maydon maydon

Information maydonda foydalanuvchining foydali ma’lumoti yoziladi. Ko’rsatkichli maydonga keyingi elementning xotiradagi adresi yoziladi. Shunday elementlardan tashkil topadigan tuzilmaga chiziqli bir bog’lamli ro’yhatlar deyiladi.Bog’langan ro’yhatlarda massivning kamchiliklari bartaraf qilinganligi sababli tuzilma uzunligi va elementlar orasidagi munosabatlar dastur bajarilishi mobaynida o’zgarib turadi. Bu dinamik tuzilma xususiyati hisoblanadi. Dinamik tuzilma deb,elementlari orasidagi munosabatlar tuzilma uzunligi (elementlar soni)dastur bajarilishi mobaynida o’zgarib turadigan tuzilmaga aytiladi. Dinamik tuzilmalarda elementlar xotirada istalgan joyda joylashishi mumkin. Shu sababli ular orasidagi munosabatlar ko’rsatkichlar orqali belgilanadi. Elementlar tuzilmaga kelib qo’shilgan paytda xotiradan bo’sh joy qidirib topiladi va elementlar joylashtiriladi. Shu sababli elementlar xotirada ketma-ket yacheykalarda joylashmagan bo’lishi mumkin. Agar fizik xotira tanqisligi sezilmasa, tuzilma uzunligi oshirilishi mumkin.Bunday tuzilmalar bilan ishlashning o’ziga yarasha afzalliklari va kamchiliklari mavjud. Afzalligi shundaki, tuzilma uzunligiga oldindan chegara qo’yilmaydi. Unga element kiritish va o’chirish amallari massivga qaraganda oson kechadi. Chunki elementlar xotiraga istalgan joyga joylashtirilayotgan paytda oldin kelib tushgan elementlar joyidan qo’zg’atilmaydi. Faqat ularning ko’rsatkichlari to’g’rilab qo’yiladi, xolos.Kamchiligi esa shundaki, oldindan mavjud bo’lgan tuzilmani massivlarda mavjud bo’lgan saralash algoritmlari bilan saralab bo’lmaydi, chunki ular elementlarning indekslari bilan bog’liq tushunchadir. Elementlarning indeksi degan tushuncha yo’qligi sababli elementlarga to’g’ridan to’g’ri murojaatning iloji yo’q, eng og’ir holatda oxirgi elementga N ta murojaat orqali yetib boriladi. Qidiruv amali ham xuddi shunday. Ya’ni eng og’ir holatda oxirgi elementni N ta solishtirishda topish mumkin.Bog’langan ro’yhatlar eng ko’p tarqalgan dinamik tuzilmalardan hisoblanadi. Ma’lumotlarni mantiqiy tasvirlash nuqtai nazaridan ro’yhatlar ikkitaga ajratiladi: chiziqli va chiziqsiz.Chiziqli ro’yhatlarda elementlar orasidagi bog’liqlik qat’iy tartiblangan bo’ladi, ya'ni element ko’rsatkichi o’zidan oldingi yoki navbatdagi element manzilini saqlaydi.Chiziqli ro’yhatlarga bir yoki ikki bog’lamli ro’yhatlar kiradi. Chiziqsiz ro’yhatlarga esa ko’p bog’lamli ro’yhatlar kiradi. Umuman olganda, ro’yhat elementlari bir yoki bir nechta ko’rsatkichli maydonlarga ega bo’lishi mumkin. Va har bir ko’rsatkichi orqali istalgan elementga murojaat qilsa, bunday ro’yhatlar chiziqsiz ro’yhatlar deyiladi. Rekursiya haqida tushuncha. Yangi obyekt yoki tushunchalarga aniq izoh kiritishning eng asosiy qoidalaridan biri bu uning ta’rifida sizga avvaldan ma’lum va tushunarli bo’lgan atamalardan foydalanib ta’rif berishdir. Shuning uchun, ta’riflarda asosano’z doirasidan chetda bo’lgan so’zlarni qo’llash noto’g’ri. Boshqa tomondan, o’z-o’zini izohlovchi dasturiy tushunchalar juda ko’p.Bunday ta'riflar rekursiv ta'riflar deb ataladi va asosan cheksiz to'plamlarga ta'rif berilganda foydalaniladi. Bunday to'plamga ta'rif berilganda, barcha elementlar ro'yhatini berish imkonsiz, va juda kata aniq to’plamlar uchun samarasiz. Shuning uchun, eng qulay usul bu obyekt o'sha to'plamga tegishli yoki tegishli emasligini aniqlash. Rekursiv ta'riflar ikki qismdan iborat. Birinchi qismida, to'plamning asos qilib olingan elementlari joylashtiriladi.Ikkinchi qismida, asos qilib olingan yoki avval foydalanilgan elementlardan foydalanilmagan holda yangi obyektlar yaratish uchun qoidalar beriladi.Bu qoidalarga yangi obyektlarni yaratishda qayta-qayta murojaat etiladi. Misol uchun, natural sonlar to'plamini yaratish uchun, bir asos element, 0, bir tomonlama, va 1 bo'yicha inkrementlash jarayoni quyidagicha beriladi:
1. 0 ∈ N; 4
2. agar n ∈ N bo'lsa, keyin (n + 1) ∈ N;
3. N to'plamda boshqa obyektlar yo'q.
Bu qoidalarga ko'ra, natural sonlar to'plami N quyidagi birliklardan tashkil topgan: 0, 0 + 1, 0 + 1 + 1, 0 + 1 + 1 + 1, va h.k. N to'plam biz natural sonlar deb atovchi obyektlarni o'z ichiga olar ekan, ta'rifga ba'zi betartib(beso'naqay) elementlar ro'yhati ham kiradi. Siz murakkab sonlar ustida maxsus spetsifikatsiyadan foydalanib arifmetik amallar bajarishni tasavvur qila olasizmi?
Shu sababli, quyidagi Arab raqamlaridan tashkil topgan ma'lum chegarali miqdorlardan foydalanaib izoh keltirish qulayroq:
1. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ∈ N;
2. agar n ∈ N bo'lsa, so'ng n0, n1, n2, n3, n4, n5, n6, n7, n8, n9 ∈ N;
3. bular natural sonlar hisoblanadi.
Demak, N asos qilib olingan 0 dan 9 gacha bo'lgan sonlardan tuzilgan kombinatsiyalardan tuzilgan sonlarni ham o'z ichiga qamrab olar ekan. Rekursiv ta'riflar ikki xil maqsadda xizmat qiladi: yuqorida qayd etilganidek, yangi elementlar yaratish va tanlangan elemeent shu to'plamga tegishli yoki tegishli emasligini testlab berish. Testlash jarayonida buni hal qilish murakkab bo'ladigan bo'lsa, u son soddaroq ko'rinishga kelmaguncha soddalashtirilib boriladi. Misol uchun, 123 natural sonmi? N to'plamni izohlovchi ta'rifdagi ikkinchi holatga asosan 123 ∈ N bo'ladi, agar 12∈ N va birinchi holatga asosan 3 ∈ N bo'lganda, 12 ∈ N bo'ladi, agar 1 ∈ N va 2 ∈ N bo'lgandava ikkalasi ham Nga tegishli bo'ladi. Berilgan misoldagidek sonni murakkab ko'rinishdan soddaroq ko'rinishga o'tkaza olish ahamiyatli, shu kabi 9.3.3 qismda ko'rib o'tadigan tez saralash usulidan foydalanish samarali. Rekursiv ta'riflar asosan raqamlar ketma-ketligi va funksiyalarni aniqlashda foydalaniladi. Misol uchun, faktorial funksiya ! quyidagi yo'sinda aniqlanishi mumkin.

Bu ta'rifdan foydalanib, biz1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, . . . sonlarini 0, 1, 2, . . . , 10, . . . raqamlarinining faktoriallarini o'z ichiga oluvchi ketma-ketlikni hozil qilishimiz mumkin.
Keyingi misol

ratsional sonlar ketma-ketligini hosil qiluvchi ta’rifdir.

Ketma-ketliklarning rekursiv ta'riflarining bitta nohush xususiyati mavjud: snketma-ketlikning elementlari qiymatini hisoblash uchun, avvalo, har bir s 1 , . . . , s n–1 larning qiymatlarini hisoblashimiz zarur bo'ladi. Misol uchun,, 3! Ni hisoblash uchun avval 0!, 1!, 2! Larning qiymatini hisoblash kerak. Bu esa ko'p hollarda noqulay vaziyatlarga olib keladi. Shuning uchun, biz bu formulaga ekvivalent bo'lgan formulani topishimiz kerak bo'ladi. Umuman olganda, bunday formulani topish murakkab masala, shunday masalaki, har doim ham o'z yechimiga ega bo'la olmaydigan muammo. Lekin bunday formula rekursiv ta'riflar uchungina mos keladi, chunki bu misolni soddalashtiradi va butun n ning qiymatini 0, 1, . . . , n – 1larning qiymatini bilmay turib hisoblash imkonini beradi. Misol uchun, g ketma-ketlikning ta'rifi:

g(n) = 2 n ko'rinishidagi sodda formulaga aylantirish mumkin bo'lar ekan. Ko'rilgan tahlillar, rekursiv ta'riflarning faqatgina teoretik ko'rinishi bo'lib, bu ta'rifdan matematikada foydalaniladi. Tabiiyki, bizning qiziqishimiz kompyuter sohasida. Dasturlash tillari grammatikasining maxsus bo'limlarida rekursiv ta'riflarga murojaat qilinadi. Grammatika yo blok diagrammalar asosida yo Backus-Naur Formasi(BNF)da aniq belgilanadi. Misol uchun, berilgan biror-bir bayonot C++ dasturlash tilidagi sintaktik tahlilidaquyidagicha blok diagramma orqali tasvirlanishi mumkin:

Tilning bir elementi hisoblanmisho'z-o'ziga murojaat qilishi bilan rekursiv aniqlanadi. Bunday ta'riflar shunday turdagi sintaktik qurilma asosida bayonot yoki atamalarning izohini aniqlashimiz mumkin bo'ladi. Rekusiv ta'riflardan dasturlashda foydalaniladi. Funksiyaning rekursiv izohlaridan foydalanish C++ dasturlash tilida juda qo'l keladi, chunki bu ortiqcha mehnat talab etmaydi.Biz oddiy formal berilgan ta'riflarni C++ tilining sintaksisiga o'girishimiz mumkin. Misol uchun, C++da faktorialga ekvivalent funksiya bu –
unsigned int factorial(unsigned int n) {
if(n==0) return 1; else returnn*factorial(n–1); }
Muammo juda kritik ko'rinadi, chunki funksiya o'z-o'zini chaqirishi orqali to'g'ri natijani bera olishini tushunish mushkul.Ko'p kompyuterlarda rekursiyalar uchun steklardan foydalanib qo'llaniladi, rekursiyani amalga oshirishning barcha ishini operatsin sistemada amalga oshiriladi, buning uchun dastur kodida ba'zi belgi;arni kiritish zarurati ham tug'ilmaydi. E. W. Dijkstra tominidan rekursiyani joriy etishda steklardan foydalanish g'oyasini bergan.Rekursiyani va uning qanday ishlashini yaxshiroq tushunish uchun funksiyaga murojaatlar jarayonini o'rganish va Sistema tomonidan amalga oshirilayotgan operatsiyalrni kuzatish ma'qul.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.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.
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. 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. SP ning qiymati o’zgarmasdan oldingi stekning holatini ko’rsatadi va 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. Bundan oldingi stek holati 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;}
Dumli rekursiya. Barcha rekursiyalar uchun aniqlanayotgan to’plam yoki funksiyaning ma’lumotlari o’zida jamlanishi kerak. Bunaqa ma’lumotlarning juda ko’p turlari joriy etilishi mumkin. Bu ma’lumotlardan ko’p marotaba, turli yo’sinlarda foydalanish mumkin. Rekursiyaning turli darajalari mavjud bo’lib, ularning murakkablik darajalari ham turlicha. Quyida, bunday turlarning ba’zilari muhokama qilinadi. Ularning oddiysi – dumli rekursiya. Dumli rekursiya faqatgina bitta rekursiv murojaatni funksiya oxirida qo’llash orqali harakterlanadi.Boshqacha qilib aytganda, murojaat bo’lganda, funksiya orqali amalga oshirilishi kerak bo’lgan birorta so’z qolmaydi; rekursiv murojaat eng so’nggi emas, unda erta bo’lmagan, to’g’ridan-to’g’ri yoki o’zlashtirma turdagilari ham mavjud. Misol uchun, tail() funksiyasi quyidagicha aniqlanadi:
void tail(int i){
if(i>0){cout< tail(i-1);} }
tail (dumli ) rekursiya li funksiyaga misol, bundaki nonTail funksiyasi quyidagicha izohlanadi:
void nonTail(int i) {
if (i > 0) {
nonTail(i-1);
cout << i << '';
nonTail(i-1);} }
Dumli rekursiya qurilishi oddiygina va kimdir tomonidan osonlikcha joylashtirilishi mumkin. Buni quyidagi I o’zgaruvchining qiymatini unga bo’lgan rekursiv murojaatlar darajasi orqali kamaytirib borish misolida ko’rish mumkin. Bunda, tail() iterativ funksiya orqali ifodalanishi mumkin:
void iterativeEquivalentOfTail(int i) {
for ( ; i > 0; i--)
cout << i << '';}
Dumli rekursiyani iteratsiya orqali foydalanishning afzalligi mavjudmi? C++ kabi tillar uchun, solishtiriladigan hech qanday foydali tomonlari bo’lmasligi mumkin, lekin Prolog kabi tillarda bu juda kata ahamiyatga ega bo’ladi. If goto bilan birga qo’llaniladigan hollarda dumli rekursiyadan foydalanmaslik ma’qul.Dumsiz rekursiya. Rekursiyalarda mavjud boshqa muammo bu qiymat kiritish qatorlarini teskari tartibda chiqarib berishdir. Quyida oddiy rekursiya qo’llanilishi berilgan:
/* 200 */ void reverse() {
char ch;
/* 201 */ cin.get(ch);
/* 202 */ if (ch != '\n') {
/* 203 */ reverse();
/* 204 */ cout.put(ch);} }
Aldab qo’yadigan joyi qayerda? Bu funksiya nimadir bajaradigandek tuyulmaydi hech. Lekin bu rekursiyaning ahamiyatliligi bilan main() ning reverse() ko’rinishidagi turi va kiritish “ABC” qatordir. Avvalo, buni faollashtirish yacheykalar orqali ch o’zgaruvchi uchun amalga oshiriladi va adresni qaytaradi. Funksiya nomi yonida void ishlatilsa funksiya hech qanaqa qiymat qaytarmaydi, shuning uchun, natija yacheykasi uchun ham hech qanaqa almashtirishlar kerak emas. get() funksiyasi birinchi belgida “A” ni o’qiydi. Chizma birinchi marotaba reverse() o’z-o’ziga murojaat qilgandagi ishga tushirish vaqt stekidagi holat ko’rsatilgan.
reverse() amalga oshirilgandagi ishga tushirish vaqt stekidagi o’zgarishlar.

Ikkinchi belgi o’qib olindi va so’nggi belgi ekanligiga tekshiriladi va unday bo’lmasa reverse()ga qayta murojaat qilinadi. Lekin har qanaqa holatda ham , ch ning qiymati qaytarilgan qiymat bo’yicha ishga tushirish vaqti stekga joylashtiriladi. Reverse 3-marotaba chqirilmasidan oldin, stekda ikki yoki undan ortiq belgilar mavjud.So’nggi belgiga yetmaguncha funksiyaga qayta-qayta murojaatlar bo’laveradi. Bizning misolimizda, reverse()ga 4 marta murojaat etilgan va so’nggi murojaatgacha bo’lgan o’zgarishlar va jarayonlarda ko’rsatilgan. To’rtinchi murojaatda, get() so’nggi belgini topadi va reverse() boshqa ishlamaydi. Sistema faollashtirish natijalaridan uning adresii qaytaradi va SPni orttirish orqali aniq bitlar yordamida bu rekordni yaroqsiz qilib tashlab yuboradi. Bajarilgan amallarni chop etish uchun 204 qatordan boshlanadi.Uchinchi murojaat faollik rekordi faol bo’lganda, ch ning qiymati, “C” harfi, birinchi belgi sifatida ekranga chiqariladi. Va nihoyat, reverse() ning birinchi murojaatining faollik rekordiga yetib kelindi. Keyin “A” chiqariladi va ekranda ko’rilishi mumkin bo’lgan qator “CBA” ko’rinishida bo’ladi. Birinchi murojaat butunlay yakunlanadi va dastur ijrosi main() da bo’ladi.
Bir xil funksiya uchun rekursiv hamda rekursiv bo’lmagan ijrolarini taqqoslang:
void simpleIterativeReverse() {
char stack[80];
register int top = 0;
cin.getline(stack,80);
for (top = strlen(stack) - 1; top >= 0; cout.put(stack[top--]));}
Funksiya ancha qisqa va balkim ozroq tushunarsiz. Xo’sh, unda farq nimada? Qisqalik va soddalikning sababi biz belgilardan tashkil topgan satr yoki massivni teskarisiga o’zgartirmoqchi bo’lganimizda ekanligini yodingizda saqlang.Bu shuni anglatadiki, strlen() va getline() ga o’xshagan funksiyalardan C++ standard kutubxonasidan foydalanishimiz mumkin. Agar bizda bunaqa funksiyalar mavjud bo’lmasa, unda bizning iterative funksiyamiz boshqacharoq bajarilishi lozim:
void iterativeReverse() {
char stack[80];
register int top = 0;
cin.get(stack[top]);
while(stack[top]!='\n')
cin.get(stack[++top]);
for (top -= 2; top >= 0; cout.put(stack[top--])); }
While ga tegishli getline() va yuqori qiymatlarning avtoinkrementi strlen() o’rnida kelgan. For esa odatdagidek xilda. Bu tahlil albatta, aniq teoretik emas, chunki butun sonlarni o’z ichiga oluvchi kiritish qatorini teskarisiga aylantirish stekning ma’lumotlar tipini char dan int ga o’zgartirgandan keyin iterativeReverse() dek bir xil bajariladi. Massiv uchun stekda foydalanilgan o’zgaruvchi nomi tasodifiy emasligini yodda tuting. Biz, shunchaki, Sistema tomonidan shubhasiz bajarilganlarni oydinlashtiramiz. Bizning stek amalga oshirish vaqti stekidan ko’proq vaqt talab etadi. Bu muhim, chunki birgina oddiy murojaatlar bunda dumli rekursiyada yetarli bo’lganidek yetarli emas. Rekersiv versiyadagi put() ham bunda hisobga olinishi zarur. iterativeReverse() funksiyasi uchun stek o’zgaruvchisi lokal ekanliginiham yodda saqlang. Shunday bo’lsada, agar global tarzda st obyekti yaratilishi talab etilsa, unda buning amalda qo’llanilishini quyidagicha yozish mumkin bo’ladi:
void nonRecursiveReverse() {
int ch;
cin.get(ch);
while (ch != '\n') {
st.push(ch);
cin.get(ch);
}
while (!st.empty()) cout.put(st.pop()); }
stek st ning funksiyadan tashqardagi e’loni bilan. iterativeReverse() ni nonRecursiveReverse()ga taqqoslagandan keyin biz shunday xulosa qilishimiz mumkinki, birinchi versiya yaxshiroq, chunki, u tezroq ishlaydi va hech qanaqa funksiya murojaatlari yo’q va funksiya o’z-o’zini qoniqtiradi, lekin nonRecursiveReverse() esa har bir iteratsiyada kamida bitta murojaatdan foydalanadi, dastur ishlashi ham sekin. Funksiya rekursiv likdan iteraktivversiyaga o’zgartirilganda , dastur aniqligiga zarar yetishi mumkin va dastur kodining qisqaligi yo’qolishi mumkin. C++dagi rekursiv funksiyalarning iteraktiv versiyalari boshqa dasturlash tillaridagi kabi uzun emas, shu sababli dastur qisqaligi ahamiyatga molik bo’lmasligi mumkin. Xulosa o’rnida, von Kochning qor uchquni qurilishini ko’rib chiqamiz. Egri chiziqlarga1904da shved matematigi Helge von Koch tomonidan ishlab chiqilgan noaniq uzunlik va atrofini qurshab olgan aniq maydonga ega bo’lgan davomiy hamda differensiallanuvchi funksiyani misol qilishimiz mumkin. Bunday egri chiziqlarga qor uchqunlarning noaniq ketma-ketligiligining limiti sifatida qarash mumkin, bularning birinchi uchtasi. Haqiqiy qor uchqunlarida bo’lganidek, bularning ikkitasi oltita gultojbargli naqshlarga ega, lekin uning algoritmini yengillashtiradigan bo’lsak, u uchta oddiy egri chiziqning birlashmasi sifatida qaraladi. Shunday egri chiziqlarning bittasi quyidagicha chiziladi:
1. Interval qismini uchta bir xil bo’laklarga bo’ling.
2. Tomonning uchdan bir qismini burchak bo’yicha harakatlantiring.
3. O’ngga 60°ga buring (yoki –60°) va tomonning uchdan bir qismini yo’naltiring.
4. Chapga 120°ga buring va qolgan uch qismida ham davom ettiring.
5. O’ngga 60°ga buring va tomon bo’ylab yana chiziq chizing.
Bu besh qadamlarning natijasi birlashtirilgan. Kompyuter grafikasi bizni juda uzoq masofalarga cho’zilishga aslo hojat qoldirmaydi, chunki agar chiziqlar piksellarning diametridan kichikroq bo’lsa, biz ekranda faqatgina bir nuqta sifatida ko’ramiz, xolos.