Mavzu. Rekursiya tushunchasi. Rekursiv triada. Iterativ va Rekursiv usullar taxlili. Misollarda solishtirish natijalarini koʻrsating Reja

Mavzu. Rekursiya tushunchasi. Rekursiv triada.Iterativ va Rekursiv usullar taxlili. Misollarda solishtirish natijalarini koʻrsating
Reja.

1. 
   Rekursiya haqida tushuncha.
   
2. 
   Funksiya murojaatlari va rekursiya joriyi
   
3. 
   Rekursiv algoritm va uning turlari.
   
4. 
   Rekursiyaga dasturlarda misollar.
   
5. 
   Xulosa.
   

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

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.
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.

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.