Telekomunikatsiya texnologiyalari va kasbiy ta’lim fakulteti

Ma'lumotlarning rekursiv turlari

Advertisement
Advertisement
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

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