O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti

7,8-ma’ruza. Rekursiv ma’lumotlar tuzilmasi.

Rekursiv algoritmlar.

Reja

1. 
   Rekursiya xaqida tushuncha.
   
2. 
   Funksiya murojaatlari va Rekursiya Joriyi
   
3. 
   Rekusiv murojaat anatomiyasi
   
4. 
   Dumli Rekursiya
   
5. 
   Dumsiz Rekursiya
   

Kalit so’zlar: rekursiya, dumli, dumsiz.
Rekursiya xaqida 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.