Vazirligi muhammad al-xorazmiy

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.