Telekomunikatsiya texnologiyalari va kasbiy ta’lim fakulteti

Rekursiv funktsiyalar va algoritmlar

Advertisement
Advertisement
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.
Advertisement
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) ".