Mavzu: Rekursiv algoritmlar va ularning vazifalari

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.