Laboratoriya ishi -7 Mavzu: Rekursiya va ularni dasturlashda ishlatish Ishdan maqsad: Ushbu

Nazorat savollari

18. 
    Rekursiya nima?
    
19. 
    Rekursiya nima maqsadda qo’llaniladi?
    
20. 
    Recursiya qanday turlarga bo’linadi?
    
21. 
    Fakratial recursion funksiya sifatida qo’llash mumkinmi?
    

LABORATORIYA ISHI - 8
Mavzu: Rekursiv va Iterativ algoritmlarni ishlatishga misollar


Ishdan maqsad: Ushbu laboratoriya ishining maqsadi talabalar rekursiv funksiyalar mavjudligini va ularning samaradorliklarini baholashni o‘rganishlari kerak. Shu asosda saralash usullarini qiyosiy tahlil qilishlari, C++ dasturlash tilida fayllar bilan ishlashni va ularga oid dasturlar tuzishni o‘zlashtirishlari kerak.
Qo‘yilgan masala: Talabalar topshiriq variantiga mos saralash usuli yordamida masalani yechish dasturini yaratish ko‘nikmasiga ega bo‘lishlari kerak.
Ish tartibi:

1. 
   Tajriba ishi nazariy ma’lumotlarini o‘rganish;
   
2. 
   Berilgan topshiriqning algoritmini ishlab chiqish;
   
3. 
   C++ dasturlash muhitida dasturni yaratish;
   
4. 
   Natijalarni tekshirish;
   
5. 
   Hisobotni tayyorlash va topshirish.
   

Matematikada rekursiya.
Matematikada rekursiya funksiyalar va sonli qatorlarning aniqlanish
metodlariga nisbatan qo’llaniladi: rekursiv ravishda berilgan funksiya o'z qiymatini boshqa argumentlar bilan chaqirish orqali aniqlanadi. Bundan holda ikkita variant mavjud:
- Tugallangan (sonli) rekursiv funksiyalar. Bunday funksiyalar chekli sondagi rekursiv murojaat (chaqiruv) uchun ixtiyoriy sonli argumentda rekursiyasiz hisoblanadigan alohida aniqlanuvchi xususiy hollardan biriga olib kelish orqali beriladi. Klassik misol: manfiy bo’lmagan butun sonning rekursiv aniqlanishi:

Bu yerda har bir keyingi rekursiv chaqiruvda argument bir birlikka kichiklashadi. Ya’ni, aniqlanishi bo’yicha manfiy bo’lmagan butun sonning faktorialini hisoblovchi funksiya argumenti n ga rekursiv murojaat qilishi 0!=1 xususiy holatga kelganda hisoblashni to’xtatadi. Shunday qilib, rekursiv aniqlanishiga qaramasdan, ixtiyoriy argument uchun bu funksiya aniqlanish sohasida tugallangan funksiya bo’ladi.

- Cheksiz rekursiv funksiyalar. Bunday funksiyalar barcha hollarda (hech bo’lmaganda ba’zi argumentlar uchun) o’z-o’ziga murojaat ko’rinishida beriladi. Misol sifatida cheksiz sonli qatorlar, cheksiz davomli kasrlar va boshqalarni olish mumkin. Amaliyotda bunday hollarda aniq qiymatni hisoblashning tabiiyki imkoni yo’q, ya’ni cheksiz vaqt talab etadi. Talab qilingan natijalar analitik usullarda topiladi. Shunga qaramay, agar absolyut aniq qiymatni olish haqida emas, balki kerakli (talab qilingan) qiymatning berilgan yaqinligini hisoblash haqida gapiradigan bo'lsak, unda ba'zi hollarda to'g'ridan-to'g'ri rekursiya ta'rifidan foydalanish mumkin: bunday holda kerakli (talab qilingan) aniqlikka erishmaguncha hisoblash davom ettiriladi. Bu kabi funksiyaga misol sifatida Eyler sonining matematik yoyilmasini olish mumkin:

Bu yerda

Yuqoridagi formuladan foydalangan holda to'g'ridan-to'g'ri hisoblash cheksiz rekursiyani keltirib chiqaradi, lekin n ning o’sib borishi bilan f(n) ning qiymati birga yaqinlashishi (intilishi)ni isbotlash mumkin (shuning uchun qatorning cheksizligiga qaramay, Eyler sonining qiymati chekli bo’ladi). Eyler soni e-ning qiymatini taxminiy hisoblash uchun rekursiya chuqurligini oldindan ma'lum bir songa sun'iy ravishda cheklash va unga erishilganda f(n)-ning qiymatiga birni ta’minlash yetarli bo’ladi.
Matematikada rekursiyaga yana bir misol sifatida rekurrent formula bilan berilgan sonli qatorlarni olish mumkin. Bunday qatorlarning har bir keyingi hadi o’zidan oldingi n ta hadga bog’liq funksiya natijasi bilan aniqlanadi.
Shunday qilib, cheklangan ifoda yordamida cheksiz qator aniqlanishi mumkin (bu ketma-ketlikning birinchi n hadlari uchun takrorlanadigan (rekurrent) formula va qiymatlar to'plamining kombinatsiyasi bo’ladi).
Matematik induksiya rekursiya bilan chambarchas bog'liq: bu natural sonlar bo'yicha o’zining kichik qiymatlari orqali berilgan rekursiv funksiya xususiyatlarini isbotlashning tabiiy usuli hisoblanadi.