Ma’ruza mashg`ulot uchun

Fibonachchi rekursiv funktsiyasi. Rekursiv funktsiyaning yana bir keng tarqalgan misoli Fibonachchi raqamlarini hisoblaydigan funksiyadir. Fibonachchi ketma-ketligining n-soni quyidagi formula bilan aniqlanadi: f (n) = f (n-1) + f (n-2) va f (0) = 0 va f (1) = 1. Ya'ni, Fibonachchi ketma-ketligi shunday ko'rinadi: 0 (0-chi davr), 1 (1-chi davr), 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, .... uchun ushbu ketma-ketlikning raqamlarini aniqlab, biz quyidagi usulni aniqlaymiz:
int Fibonachi(int n)
{
if (n == 0 || n == 1) return n;
return Fibonachi(n - 1) + Fibonachi(n - 2);
}
int fib4 = Fibonachi(4);
int fib5 = Fibonachi(5);
int fib6 = Fibonachi(6);
Console.WriteLine("4 fibonachchi son= "+fib4);
Console.WriteLine("5 fibonachchi son= "+fib5);
Console.WriteLine("6 fibonachchi son= "+fib6);

Bu erda asosiy versiya quyidagicha ko'rinadi:

if (n == 0 || n == 1) return n;
Ya'ni, agar biz ketma-ketlikning nol yoki birinchi elementini qidiradigan bo'lsak, u holda xuddi shu raqam qaytariladi - 0 yoki 1. Aks holda, Fibonachi (n - 1) + Fibonachi (n - 2) ifodasi natijasi;


Rekursiyalar va sikllar
Bu rekursiya qanday ishlashini tushunishga yordam beradigan rekursiv funksiyalarning eng oddiy misolidir. Shu bilan birga, ikkala funksiya uchun ham rekursiyalar o'rniga loop konstruksiyalaridan foydalanishingiz mumkin. Umuman olganda, tsiklga asoslangan alternativalar rekursiyaga qaraganda tezroq va samaraliroq. Masalan, sikllar yordamida Fibonachchi raqamlarini hisoblash:
static int Fibonachi2(int n)
{
int result = 0;
int b = 1;
int tmp;
for (int i = 0; i < n; i++)
{
tmp = result;
result = b;
b += tmp;
}
return result;
}

Shu bilan birga, ba'zi holatlarda rekursiya maqbul yechimni taqdim etadi, masalan, turli xil daraxt ko'rinishlarini, masalan, kataloglar va fayllar daraxtini kesib o'tishda.