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,
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.
Umumiy rekursiya alternativa:
Ko'pgina taniqli rekursiv algoritmlar berilgan ma'lumotlardan butunlay yangi ma'lumotlar hosil qiladi va ular ustida takrorlanadi. HtDP (Dasturlarni qanday tuzish kerak) ushbu turni generativ rekursiya deb ataydi. Generativ rekursiya misollariga quyidagilar kiradi: gcd, tezkor, ikkilik qidirish, mergesort, Nyuton usuli, fraktallar va adaptiv integratsiya.
Ushbu farq muhim ahamiyatga ega bekor qilinishini isbotlash funktsiya.
Sonli barcha strukturaviy rekursiv funktsiyalar (induktiv ravishda aniqlangan ) ma'lumotlar tuzilmalarini tugatish orqali osongina ko'rsatish mumkin tarkibiy induksiya: intuitiv ravishda, har bir rekursiv qo'ng'iroq, asosiy holatga kelguncha, kirish ma'lumotlarining kichik qismini oladi.
Generativ rekursiv funktsiyalar, aksincha, ularning rekursiv chaqiruvlariga kichikroq ma'lumot kiritishi shart emas, shuning uchun ularning bekor qilinishini isbotlash shunchaki oddiy emas va oldini olish cheksiz ilmoqlar katta g'amxo'rlikni talab qiladi. Ushbu generativ rekursiv funktsiyalarni ko'pincha o'zaro faoliyat funktsiyalari sifatida talqin qilish mumkin - har bir qadam yangi ma'lumotlarni hosil qiladi, masalan Nyuton usulida ketma-ket yaqinlashish - va bu korrekturani tugatish ma'lumotlar oxir-oqibat ba'zi shartlarni qondirishini talab qiladi, bu kafolat berilishi shart emas.
Xususida pastadir variantlari, strukturaviy rekursiya - bu cheklangan boshlanadigan va har bir rekursiv bosqichda kamayib boradigan aniq tsikl varianti, ya'ni hajmi yoki murakkabligi.
Aksincha, generativ rekursiya - bu shunday aniq tsikl variantining mavjud emasligi va tugatish funktsiyaga bog'liq, masalan, "yaqinlashish xatosi" nolga tushishi shart emas va shuning uchun qo'shimcha tahlillarsiz tugatish kafolatlanmaydi.
Mavzuga doir misollar.
|
