Mavzu: Rekursiv funktsiyalar va ularning algoritmlar

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