Oʻzbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xozazmiy nomidagi toshkent axborot texnologiyalari

OʻZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XOZAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

TELEKOMMUNIKATSIYA TEXNOLOGIYALARI
Fakulteti 414-20 guruh
Ma’lumotlar tuzilmasi va algoritmlari fanidan
MUSTAQIL ISHI

Bajardi: Ortiqov N.A
Tekshirdi: Xojieva N.J

TOSHKENT – 2021


Mavzu: Rekursiyavaunidasturlashdaishlatish.
Reja:
1.Kirish.
2.Rekursiya.
3.Rekursiv funksiyalar.
4. C++ dasturlash tilida rekursiv funksiyalar.
5.Xulosa.
6.Foydalanilgan adabiyotlar.
Kalit so’zlar: rekursiya, fibonachi qatori, rekursiv funksiya, Rekurrent qatorlar, Cheksiz qatorlar
Maqsad: Mavzudan maqsan rekursiya va rekursiv funksiyalar haqida tushunchaga ega bo’lish. Rekursiv funksiyalarni dasturlashda ishlatilishini o’rganish hamda uning ustida amallarni ko’rib chiqish.
Kirish
Rekursiya bu bir xil muammoning kichik nusxalarini echimiga bog'liq bo'lgan muammoni hal qilish usuli. Bunday muammolarni odatda hal qilish mumkin takrorlash, lekin buning uchun dasturlash vaqtida kichikroq misollarni aniqlash va indekslash kerak. Rekursiya buni hal qiladi rekursiv muammolar yordamida funktsiyalari o'zlarining kodlari ichidan o'zlarini chaqirishadi. Ushbu yondashuv ko'plab turdagi muammolarda qo'llanilishi mumkin va rekursiya kompyuter fanining markaziy g'oyalaridan biridir.
Rekursiyaning kuchi, shubhasiz, cheklangan bayonot bilan cheksiz ob'ektlar to'plamini aniqlash imkoniyatida. Xuddi shu tarzda, cheksiz sonli hisob-kitoblarni cheklangan rekursiv dastur bilan tavsiflash mumkin, hatto bu dasturda aniq takrorlash bo'lmasa ham.
— Niklaus Virt
Asosiy qism
Funktsiya o'z – o'zini chaqirishi rekursiya deyiladi. U ikki xil – to'g'ri rekursiya va bilvosita rekursiya bo'lishi mumkin. Agarda funktsiya o'zini o'zi chaqirsa bu to'g'ri rekursiya deyiladi. Agarda funktsiya boshqa bir funktsiyani chaqirsa va u funktsiya o'z navbatida birinchisini chaqirishi esa bilvosita rekursiya deyiladi.
Ayrim muammolar rekursiya yordamida osonroq echiladi. Agarda ma'lumotlar ustida biror protsedura ishlatilsa va uning natijasi ustida ham xuddi shu protsedura bajarilsa, bunday hollarda rekursiyani ishlatish lozim. Rekursiya ikki xil natija bilan yakunlanadi: u yoki oxir – oqibat albatta tugaydi va biror natija qaytaradi, ikkinchisi hech qachon tugallanmaydi va xatolik qaytaradi.

Agarda funktsiya o'zini o'zi chaqirsa, bu funktsiyani nusxasi chaqirilishini aytib o'tish lozim. Rekursiya yordamida echiladigan muammo sifatida Fibonachchi qatorini ko'rsatish mumkin.

1, 1, 2, 3, 5, 8, 13, 21, 34 …

Bu qatorning har bir soni (ikkinchisidan keyin) o'zidan oldingi ikki sonning yig’indisiga teng. Masala quyidagidan iborat: Fibonachi qatorini 12 – a'zosi nechaga tengligini aniqlang. Bu muammoning echishning usullaridan biri qatorni batafsil tahlil qilishdan iboratdir. qatorning oldingi ikki soni birga teng. har bir navbatdagi son oldingi ikkita sonning yig’indisiga teng. Ya'ni, o'n yettinchi son o'n oltinchi va o'n beshinchi sonlar yig’indisiga teng. Umumiy holda n – sonning yig’indisi (n-2)- va (n-1) – sonlarning yig’indisiga teng (n>2 hol uchun).

Rekursiv funktsiyalar uchun rekursiyani to'xtatish shartini berish zarur. Fibonachchi qatori uchun to'xtatish sharti n<3 shartidir.

Bunda quyidagi algoritm qo'llaniladi:

1.Foydalanuvchidan Fibonachi qatorining qaysi a'zosini hisoblashini ko'rsatishini so'raymiz.
2.fib() funktsiyasini chaqiramiz va unga foydalanuvchi tomonidan berilgan Fibonachchi qatori a'zosi tartib nomerini argument sifatida uzatamiz.
3.fib() funktsiyasi (n) argumentni tahlil qiladi. Agarda n<3 bo'lsa, funktsiya 1 qiymat qaytaradi; aks holda fib() funktsiyasi o'zini o'zi chaqiradi va unga argument sifatida n–2 qiymatni beradi, keyin yana o'z–o'zini chaqiradi va bu funktsiyaga n–1 ni qiymat sifatida beradi. Bundan keyin esa ularning yig’indisini qiymat sifatida uzatadi.
Agarda fib(1) funktsiyasi chaqirilsa u 1 qiymatni qaytaradi. Agarda fib(2) funktsiyasi chaqirilsa u ham 1 qiymatni qaytaradi. Agarda fib(3) funktsiyasi chaqirilsa u fib(1) va fib(2) funktsiyalarini yig’indisini qaytaradi. fib(2) va fib(1) funktsiyalari 1 qiymatni qaytarganligi sababli fib(3) funktsiyasi qiymati 2 ga teng bo'ladi.

Agarda fib(4) funktsiyasi chaqirilsa, bunda u fib(3) va fib(2) funktsiyalari yig’indisini qiymat sifatida qaytaradi. fib(3) funktsiyasi 2 va fib(2) funktsiyasi 1 qiymat qaytarishidan fib(4) funktsiyasi 3 ni qiymat sifatida qaytarishi kelib chiqadi. Demak, Fibonachchi qatorining to'rtinchi a'zosi 3 ga teng ekan.

Yuqorida, tavsiflangan usul bu masalani echishda unchalik samarali usul emas. fib(20) funktsiyasi chaqirilsa, u tomonidan fib() funktsiyasi 13529 marta chaqiriladi. Bunday hollarda ehtiyot bo'lish lozim. Agarda Fibonachchi qatorining juda katta nomerini bersak xotira etishmasligi mumkin. Fib() funktsiyasini har safar chaqirilishida xotiradan ma'lum bir soha zahiralanadi. Funktsiyadan qaytish bilan xotira bo'shatiladi. Lekin, rekursiv tarzda funktsiya chaqirilsa xotiradan uning uchun yangi joy ajratiladi va toki ichki funktsiya o'z ishini tugatmaguncha uni chaqirgan funktsiya egallagan joy bo'shatilmaydi.