Mustaqil ishi Mavzu: Rekursiya va uni dasturlashda ishlatish rekursiv algoritmlar ularning tahlili

Ma’lumotlar Tuzilmasi va Algoritmlar

Fanidan
Mustaqil ishi

Mavzu: Rekursiya va uni dasturlashda ishlatish rekursiv algoritmlar ularning tahlili.
Bajardi: Shomurodov .P

Qabul qildi: Abloqulov.K.B

Reja:

1. 
   Rekursiv funktsiyalar va algoritmlar.
   
2. 
   Ma'lumotlarning rekursiv turlari.
   
3. 
   Rekursiya turlari.
   
4. 
   Mavzuga doir misollar.
   
5. 
   Foydalanilgan adabiyotlar.
   

Rekursiv funktsiyalar va algoritmlar.

Umumiy kompyuter dasturlash taktika - bu muammoni asl nusxadagi bir xil turdagi pastki muammolarga ajratish, ushbu kichik muammolarni echish va natijalarni birlashtirish. Bunga ko'pincha ajratish va zabt etish usuli; a bilan birikganda qidiruv jadvali sub-muammolarni echish natijalarini saqlaydigan (ularni qayta-qayta hal qilmaslik va qo'shimcha hisoblash vaqtiga yo'l qo'ymaslik uchun) dinamik dasturlash yoki yod olish.
Rekursiv funktsiya ta'rifi bir yoki bir nechtasiga ega asosiy holatlar, funktsiya natijani beradigan kirish (lar) ni anglatadi ahamiyatsiz (takrorlanmasdan), va bitta yoki bir nechtasi rekursiv holatlar, dastur takrorlanadigan kirish (lar) ni anglatadi (o'zini o'zi chaqiradi). Masalan, faktorial funktsiyani tenglamalar bilan rekursiv ravishda aniqlash mumkin 0! = 1 va hamma uchun n > 0, n! = n(n − 1)!. Ikkala tenglama ham o'z-o'zidan to'liq ta'rifni tashkil etmaydi; birinchisi - asosiy, ikkinchisi - rekursiv holat. Asosiy ish rekursiya zanjirini uzganligi sababli, ba'zan uni "tugatuvchi ish" ham deyishadi.
Rekursiv holatlarning ishi murakkab yozuvlarni oddiylariga ajratish sifatida qaralishi mumkin. To'g'ri ishlab chiqilgan rekursiv funktsiyasida, har bir rekursiv chaqiriq bilan, kiritish muammosi shunday soddalashtirilishi kerakki, oxir-oqibat asosiy holatga erishish kerak. (Oddiy sharoitlarda tugatish uchun mo'ljallanmagan funktsiyalar - masalan, ba'zilari tizim va server jarayonlari - bu bundan mustasno.) Asosiy ishni yozishga beparvolik qilish yoki uni noto'g'ri tekshirish, sabab bo'lishi mumkin cheksiz pastadir.

Ba'zi funktsiyalar uchun (masalan, seriyali uchun e = 1/0! + 1/1! + 1/2! + 1/3! + ...) kirish ma'lumotlari nazarda tutilgan aniq bazaviy holat mavjud emas; chunki bu qo'shilishi mumkin parametr (masalan, qator misolida qo'shiladigan atamalar soni kabi) asosiy holatni o'rnatadigan "to'xtash mezonini" ta'minlash uchun. Bunday misol tabiiy ravishda davolanadi kelishuv,[Qanaqasiga? ] bu erda mahsulotning ketma-ket shartlari qisman yig'indilar; buni indeksatsiya parametridan foydalanib, "hisoblash" deyish bilan rekursiyaga o'tkazish mumkin nth muddat (nth qisman sum) ".

Ma'lumotlarning rekursiv turlari.
Ko'pchilik kompyuter dasturlari o'zboshimchalik bilan katta miqdordagi ishlov berish yoki ishlab chiqarishi kerak ma'lumotlar. Rekursiya - aniq o'lchamlari noma'lum bo'lgan ma'lumotlarni aks ettirish usuli dasturchi: dasturchi ushbu ma'lumotni a bilan belgilashi mumkin o'z-o'ziga havola ta'rifi. O'z-o'ziga yo'naltirilgan ta'riflarning ikki turi mavjud: induktiv va koinduktiv ta'riflar.

Qo'shimcha ma'lumotlar: Algebraik ma'lumotlar turi

Induktiv ravishda aniqlangan ma'lumotlar
Asosiy maqola: Rekursiv ma'lumotlar turi
Ma'lumotlarning induktiv ravishda aniqlangan rekursiv ta'rifi - bu ma'lumotlarning misollarini qanday tuzishni belgilaydigan tushuncha. Masalan, bog'langan ro'yxatlar induktiv ravishda belgilanishi mumkin (bu erda, yordamida Xaskell sintaksis):

ma'lumotlar ListOfStrings = EmptyList | Kamchiliklari Ip ListOfStrings

Yuqoridagi kod bo'sh bo'lgan satrlar ro'yxatini yoki satr va qatorlar ro'yxatini o'z ichiga olgan tuzilmani belgilaydi. Ta'rifdagi o'z-o'ziga mos yozuvlar har qanday (cheklangan) sonli qatorlarning ro'yxatlarini tuzishga imkon beradi.

Induktivning yana bir misoli ta'rifi bo'ladi natural sonlar (yoki ijobiy butun sonlar ):

Natural son yo 1 yoki n + 1, bu erda n natural son.
Xuddi shunday rekursiv ta'riflar ning tuzilishini modellashtirish uchun ko'pincha ishlatiladi iboralar va bayonotlar dasturlash tillarida. Til dizaynerlari ko'pincha sintaksisdagi grammatikalarni ifoda etadilar Backus-Naur shakli; Ko'paytirish va qo'shish bilan oddiy arifmetik iboralar tili uchun mana shunday grammatika:
::= | ( * ) | ( + )
Bu shuni anglatadiki, ifoda - bu raqam, ikkita ifodaning hosilasi yoki ikkita ifodaning yig'indisi. Ikkinchi va uchinchi qatorlardagi ifodalarga rekursiv ravishda murojaat qilib, grammatika o'zboshimchalik bilan murakkab arifmetik ifodalarga ruxsat beradi. (5 * ((3 * 6) + 8)), bitta ifodada bir nechta mahsulot yoki sum operatsiyasi bilan.

Rekursiya turlari.

Yagona rekursiya va ko'p martalik rekursiya
Faqat bitta o'ziga xos ma'lumotni o'z ichiga olgan rekursiya quyidagicha tanilgan bitta rekursiya, bir nechta o'z-o'ziga havolalarni o'z ichiga olgan rekursiya sifatida tanilgan ko'p rekursiya. Yagona rekursiyaning standart namunalari qatorlarni kesib o'tishni o'z ichiga oladi, masalan, chiziqli qidirish yoki faktorial funktsiyani hisoblash, ko'p takrorlashning standart namunalari esa daraxtlarni kesib o'tish, masalan, birinchi chuqurlikdagi qidiruvda.

Yagona rekursiya ko'p martalik rekursiyadan ancha samaraliroq bo'ladi va odatda uni chiziqli vaqt ichida ishlaydigan va doimiy bo'shliqni talab qiladigan takrorlanadigan hisoblash bilan almashtirish mumkin. Ko'p rekursiya, aksincha, eksponent vaqt va makonni talab qilishi mumkin va asosan rekursiv bo'lib, aniq stack holda takrorlash bilan almashtirilmaydi.

Ba'zan bir nechta rekursiya bitta rekursiyaga o'tkazilishi mumkin (va agar kerak bo'lsa, u erdan takrorlashga). Masalan, Fibonachchi ketma-ketligini hisoblash sodda ravishda takrorlanishdir, chunki har bir qiymat oldingi ikkita qiymatni talab qiladi, uni ketma-ket ikkita qiymatni parametr sifatida o'tkazib bitta rekursiya bilan hisoblash mumkin. Bu tabiiy ravishda, dastlabki qiymatlardan kelib chiqib, har bir qadamda ketma-ket ikkita qadriyatlarni kuzatib boradigan korecurion sifatida belgilangan - qarang uzatish: misollar. A dan foydalangan holda yanada murakkab bir misol ipli ikkilik daraxt, bu ko'p marta takrorlanishga emas, balki takrorlanadigan daraxtlarni kesib o'tishga imkon beradi.

Bilvosita rekursiya

Asosiy maqola: O'zaro rekursiya
Rekursiyaning asosiy namunalari va bu erda keltirilgan misollarning aksariyati namoyish etadi to'g'ridan-to'g'ri rekursiya, unda funktsiya o'zini o'zi chaqiradi. Bilvosita rekursiya funktsiyani o'zi emas, balki o'zi chaqirgan boshqa funktsiya (to'g'ridan-to'g'ri yoki bilvosita) chaqirganda paydo bo'ladi. Masalan, agar f qo'ng'iroqlar f, bu to'g'ridan-to'g'ri rekursiya, ammo agar shunday bo'lsa f qo'ng'iroqlar g qo'ng'iroq qiladi f, unda bu bilvosita rekursiya f. Uch yoki undan ortiq funktsiyalarning zanjirlari mumkin; Masalan, 1-funktsiya 2-funktsiyani chaqiradi, 2-funktsiya 3-funktsiyani chaqiradi va 3-funktsiya yana 1-funktsiyani chaqiradi.

Bilvosita rekursiya ham deyiladi o'zaro rekursiya, bu ko'proq nosimmetrik atama, ammo bu shunchaki diqqatning farqi, boshqacha tushuncha emas. Ya'ni, agar f qo'ng'iroqlar g undan keyin g qo'ng'iroqlar f, bu o'z navbatida qo'ng'iroq qiladi g yana, nuqtai nazardan f yolg'iz, f nuqtai nazaridan bilvosita takrorlanuvchi hisoblanadi g yolg'iz o'zi bilvosita takrorlanadi, ikkalasi nuqtai nazaridan f va g bir-birlarini o'zaro takrorlashmoqda. Xuddi shunday bir-birini chaqiradigan uchta yoki undan ortiq funktsiyalar to'plamini o'zaro rekursiv funktsiyalar to'plami deb atash mumkin.

Anonim rekursiya
Asosiy maqola: Anonim rekursiya
Rekursiya odatda funktsiyani nomiga aniq qo'ng'iroq qilish orqali amalga oshiriladi. Shu bilan birga, rekursiya, ayniqsa, juda foydali bo'lgan hozirgi kontekstga asoslangan funktsiyani bevosita chaqirish orqali ham amalga oshirilishi mumkin noma'lum funktsiyalar, va sifatida tanilgan anonim rekursiya.

Strukturaviy va generativ rekursiya

Shuningdek qarang: Strukturaviy rekursiya
Ba'zi mualliflar rekursiyani "tizimli" yoki "generativ" deb tasniflashadi. Ajratish rekursiv protsedura ishlaydigan ma'lumotlarni qaerdan olishi va ushbu ma'lumotlarni qanday qayta ishlashi bilan bog'liq.

[Tuzilgan ma'lumotlarni iste'mol qiladigan funktsiyalar] odatda o'zlarining argumentlarini o'zlarining bevosita tarkibiy qismlariga ajratadi va keyin ushbu tarkibiy qismlarni qayta ishlaydi. Agar bevosita komponentlardan biri kirish bilan bir xil ma'lumotlarga tegishli bo'lsa, funktsiya rekursivdir. Shu sababli, biz ushbu funktsiyalarni (TUZUVCHI) RECURSIVE FUNKSIYALAR deb ataymiz.

— Felleyzen, Findler, Flatt va Krishnaurti, Dasturlarni qanday tuzish kerak,
Shunday qilib, strukturaviy rekursiv funktsiyani belgilovchi xususiyati shundaki, har bir rekursiv chaqiriqning argumenti dastlabki kirish maydonining mazmunidir. Strukturaviy rekursiya deyarli barcha daraxtlar bo'ylab o'tishni o'z ichiga oladi, shu jumladan XMLni qayta ishlash, daraxtlarni ikkilamchi yaratish va qidirish va hk. Tabiiy sonlarning algebraik tuzilishini (ya'ni tabiiy son nolga yoki tabiiy sonning vorisiga teng) hisobga olib, bunday funktsiyalarni o'z ichiga oladi. faktorial sifatida tarkibiy rekursiya sifatida qaralishi mumkin.

Umumiy rekursiya alternativa:

Ko'pgina taniqli rekursiv algoritmlar berilgan ma'lumotlardan butunlay yangi ma'lumotlar hosil qiladi va ular ustida takrorlanadi. HtDP (Dasturlarni qanday tuzish kerak) ushbu turni generativ rekursiya deb ataydi. Generativ rekursiya misollariga quyidagilar kiradi: gcd, tezkor, ikkilik qidirish, mergesort, Nyuton usuli, fraktallar va adaptiv integratsiya.

— Matthias Felleisen, Murakkab funktsional dasturlash, 2002[6]

Ushbu farq muhim ahamiyatga ega bekor qilinishini isbotlash funktsiya.

Sonli barcha strukturaviy rekursiv funktsiyalar (induktiv ravishda aniqlangan ) ma'lumotlar tuzilmalarini tugatish orqali osongina ko'rsatish mumkin tarkibiy induksiya: intuitiv ravishda, har bir rekursiv qo'ng'iroq, asosiy holatga kelguncha, kirish ma'lumotlarining kichik qismini oladi.

Generativ rekursiv funktsiyalar, aksincha, ularning rekursiv chaqiruvlariga kichikroq ma'lumot kiritishi shart emas, shuning uchun ularning bekor qilinishini isbotlash shunchaki oddiy emas va oldini olish cheksiz ilmoqlar katta g'amxo'rlikni talab qiladi. Ushbu generativ rekursiv funktsiyalarni ko'pincha o'zaro faoliyat funktsiyalari sifatida talqin qilish mumkin - har bir qadam yangi ma'lumotlarni hosil qiladi, masalan Nyuton usulida ketma-ket yaqinlashish - va bu korrekturani tugatish ma'lumotlar oxir-oqibat ba'zi shartlarni qondirishini talab qiladi, bu kafolat berilishi shart emas.
Xususida pastadir variantlari, strukturaviy rekursiya - bu cheklangan boshlanadigan va har bir rekursiv bosqichda kamayib boradigan aniq tsikl varianti, ya'ni hajmi yoki murakkabligi.
Aksincha, generativ rekursiya - bu shunday aniq tsikl variantining mavjud emasligi va tugatish funktsiyaga bog'liq, masalan, "yaqinlashish xatosi" nolga tushishi shart emas va shuning uchun qo'shimcha tahlillarsiz tugatish kafolatlanmaydi.
Mavzuga doir misollar.