Mavzu: Rekursiv funktsiyalar va ularning algoritmlar

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


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.