С# dasturlash tilida rekursiv funksiyalar

С# DASTURLASH TILIDA REKURSIV FUNKSIYALAR

Ushbu maqola muammolarni hal qilishning rekursiv yondashuvlari haqida. Rekursiya bo'yicha dalillar uchun qarang Matematik induksiya. Informatika qisqartmalaridagi rekursiya uchun qarang Rekursiv qisqartirish § Kompyuter bilan bog'liq misollar.

Yordamida yaratilgan daraxt Asosiy dasturlash tili va rekursiyaga katta ishonish. Har bir novdani daraxtning kichikroq versiyasi sifatida ko'rish mumkin.

Yilda Kompyuter fanlari, rekursiya bu bir xil muammoning kichik nusxalarini echimiga bog'liq bo'lgan muammoni hal qilish usuli.^[1] Bunday muammolarni odatda hal qilish mumkin takrorlash, lekin buning uchun dasturlash vaqtida kichikroq misollarni aniqlash va indekslash kerak. Rekursiya buni hal qiladi rekursiv muammolar yordamida funktsiyalari o'zlarining kodlari ichidan o'zlarini chaqirishadi. Ushbu yondashuv ko'plab turdagi muammolarda qo'llanilishi mumkin va rekursiya kompyuter fanining markaziy g'oyalaridan biridir.^[2]

Rekursiyaning kuchi, shubhasiz, cheklangan bayonot bilan cheksiz ob'ektlar to'plamini aniqlash imkoniyatida. Xuddi shu tarzda, cheksiz sonli hisob-kitoblarni cheklangan rekursiv dastur bilan tavsiflash mumkin, hatto bu dasturda aniq takrorlash bo'lmasa ham.

— Niklaus Virt, Algoritmlar + Ma'lumotlar tuzilmalari = Dasturlar, 1976^[3]

Ko'pgina kompyuterlar dasturlash tillari funktsiyani o'z kodidan chaqirishga imkon berish orqali rekursiyani qo'llab-quvvatlash. Biroz funktsional dasturlash tillar (masalan, Klojure)^[4] hech qanday tsikl konstruktsiyalarini aniqlamang, lekin kodni qayta-qayta chaqirish uchun faqat rekursiyaga asoslang. Bu isbotlangan hisoblash nazariyasi faqat ushbu rekursiv tillar Turing tugadi; bu shuni anglatadiki, ular qanchalik kuchli bo'lsa (ular bilan bir xil muammolarni hal qilishda foydalanish mumkin) imperativ tillar kabi boshqaruv tuzilmalariga asoslangan esa va uchun.

Funktsiyani o'z ichidan qayta-qayta chaqirish sabab bo'lishi mumkin chaqiruv to'plami barcha jalb qilingan qo'ng'iroqlarning kirish o'lchamlari yig'indisiga teng o'lchamga ega bo'lish. Bundan kelib chiqadiki, takrorlanish yordamida osonlikcha echilishi mumkin bo'lgan muammolar uchun rekursiya odatda kamroq bo'ladi samarali, va katta muammolar uchun optimallashtirish usullaridan foydalanish juda muhimdir quyruq chaqiruvi optimallashtirish.^{[iqtibos kerak]}
Rekursiv funktsiyalar va algoritmlar

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.

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

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.

Qo'shimcha ma'lumotlar: Algebraik ma'lumotlar turi

Induktiv ravishda aniqlangan ma'lumotlar

Asosiy maqola: Rekursiv ma'lumotlar turi

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.

Koinduktiv ravishda aniqlangan ma'lumotlar va o'zaro kelishuv

Asosiy maqolalar: Coinduction va Xizmat

Ma'lumotlarning koinduktiv ta'rifi - bu ma'lumotlarning bir qismida bajarilishi mumkin bo'lgan operatsiyalarni belgilaydigan tushuncha; odatda, cheksiz kattalikdagi ma'lumotlar tuzilmalari uchun o'z-o'ziga yo'naltirilgan koinduktiv ta'riflardan foydalaniladi.

Cheksizning koinduktiv ta'rifi oqimlar norasmiy ravishda berilgan qatorlar quyidagicha ko'rinishi mumkin:

Iplar oqimi bu shunday ob'ekt s: bosh (lar) - bu ip, dum (lar) - bu torlar oqimi.

Bu satrlar ro'yxatining induktiv ta'rifiga juda o'xshaydi; farqi shundaki, ushbu ta'rif ma'lumotlar tuzilmasi tarkibiga, ya'ni kiruvchi funktsiyalari bosh va quyruq- va bu tarkib nimadan iborat bo'lishi mumkin, ammo induktiv ta'rif strukturani qanday yaratishni va nimadan yaratilishi mumkinligini belgilaydi.

Corecursion koinduksiya bilan bog'liq bo'lib, cheksiz ob'ektlarning (ehtimol) alohida misollarini hisoblash uchun ishlatilishi mumkin. Dasturlash texnikasi sifatida u ko'pincha kontekstida ishlatiladi dangasa dasturlash tillari va kerakli natijalar yoki dastur natijalari noma'lum bo'lgan hollarda rekursiyadan afzalroq bo'lishi mumkin. Bunday hollarda dastur cheksiz katta (yoki cheksiz aniq) natija uchun ta'rifni va natijaning cheklangan qismini olish mexanizmini talab qiladi. Birinchi n ni hisoblash muammosi tub sonlar bu corecursive dasturi bilan echilishi mumkin bo'lgan narsadir (masalan. Bu yerga).

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.

Strukturaviy va generativ rekursiya

Shuningdek qarang: Strukturaviy 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, 2001^[5]

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.