С# dasturlash tilida rekursiv funksiyalar

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, fraktallarva 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.
  

Rekursiv dasturlar

Rekursiv protseduralar

Faktorial

Rekursiv protseduraning klassik namunasi - hisoblash uchun ishlatiladigan funktsiya faktorial a tabiiy son:

Psevdokod (rekursiv):