Mavzu: Rekursiv funktsiyalar va ularning algoritmlar

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.

— Matthias Felleisen, Murakkab funktsional dasturlash, 2002[6]

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.

Xulosa.

Rekursiv funksiyalar va ularning algoritmlari, dasturlashda muhim va qo'pol bo'lgan vositalardir. Bu funksiyalar ko'p turli muammolar yoki hisoblash jarayonlarini yechish uchun qo'llaniladi. Rekursiv funksiyalar o'zlarini chaqirib turishi mumkin bo'lgan funksiyalardir. Ular o'qilishi va tushunilishi qulay bo'lgan algoritmlarni yaratishda yordam beradi. Shuningdek, rekursiv funksiyalarni yozirishda, o'zini chaqirishlar sonini cheklash shartlarini qo'shish juda muhim. Bu, funksiyalar to'xtatish uchun kerakli shartlar bilan shuhratlantirish uchun foydali bo'ladi.

Foydalanilgan Adabiyotlar.