Rekursiv funksiyalar

Fibonachchi sonlarini topish masalasi
Fibonachchi sonlari qyidagicha aniqlanadi:

Fibonachchi sonlaridan hosil bo‘lgan ketma-ketlikning n – hadi topilsin. Rekursiyani qo‘llagan holda fibonachchi sonlarini topish formulasini quyidagicha yozish mumkin:

using System;
class Program
{
static void Main(string[] args)
{
int firstFibNum, secondFibNum, n,p;
Console.Write(" Nolinchi fibonachchi sonini kiriting: ");
firstFibNum = Convert.ToInt32(Console.ReadLine());
Console.Write(" Birinchi fibonachchi sonini kiriting: ");
secondFibNum = Convert.ToInt32(Console.ReadLine());
Console.Write(" Qidirilayotgan fibonachchi soni o‘rnini kiriting: ");
n = Convert.ToInt32(Console.ReadLine());
p = rFibNum(firstFibNum, secondFibNum, n);
Console.WriteLine(" "+n + " – o‘rindagi Fibonachchi soni: " + p);
Console.ReadKey();
}
static int rFibNum(int a, int b, int n)
{
if (n == 0) return a;
else if (n == 1) return b;
return rFibNum(a, b, n - 1) + rFibNum(a, b, n - 2);
}
}
Rekursiya chiroyli, ixcham ko‘ringani bilan xotirani tejash va hisoblash vaqtini qisqartirish nuqtai-nazaridan uni imkon qadar iterativ hisoblash bilan almashtirilgani ma’qul. Masalan, x haqiqiy sonining n-darajasini hisoblashning quyidagi yechim varianti nisbatan kam resurs talab qiladi (n – butun ishorasiz son):

using System;

class Program
{
static void Main(string[] args)
{
double x,p;
int n;
Console.Write(" x = ");
x = Convert.ToDouble(Console.ReadLine());
n = Convert.ToInt32(Console.ReadLine());
p = Butun_Daraja(x, n);
Console.WriteLine(" "+x + " – ni "+n+" darajasi = " + p);
Console.ReadKey();
}
static double Butun_Daraja(double x, int n)
{
double p = 1;
for (int i = 1; i <= n; i++) p *= x;
return p;
}

}
Ikkinchi tomondan, shunday masalalar borki, ularni yechishda rekursiya juda samarali, hattoki yagona usuldir. Xususan, grammatik tahlil masalalarida rekursiya juda oson hisoblanadi.

“Xanoy minorasi”masalasi

Uchta A, B, C qoziq va n-ta har xil o‘lchamli xalqalar mavjud. Xalqalarni o‘lchamlari o‘sish tartibida 1 dan n gacha tartiblangan. Qolgan barcha xalqalar A qoziqqa rasmdagidek joylashtirilgan. A qoziqdagi barcha xalqalarni C qoziqqa, yordamchi B qoziqdan foydalangan holda, quyidagi qoidalarga amal qilgan holda o‘tkazish talab etiladi: xalqalarni bittadan ko‘chirish kerak va katta o‘lchamli xalqani kichik o‘lchamli xalqa ustiga qo‘yish mumkin emas.

using System;

class Program
{
static void Main(string[] args)
{
int Xalqalar_Soni;
Console.WriteLine(" Hanoy minorasi masalasi");
Console.Write(" Xalqalar sonini kiriting: ");
Xalqalar_Soni=Convert.ToInt32(Console.ReadLine());
Hanoy(Xalqalar_Soni);
Console.ReadKey();
}
static void Hanoy(int n, char a = 'A', char b = 'C', char c = 'B')
{
if(n>0)
{
Hanoy(n-1, a, c, b);
Console.WriteLine(" Xalqa "+a+" dan "+b+" ga o‘tkazilsin\n");
Hanoy(n-1, c, b, a);
}
}
}

Xalqalar soni 3 bo‘lganda dastur quyidagi sxema bo‘yicha ishlaydi:

Dastur xalqalar soni 3 bo‘lganda (Xalqalar_Soni=3) ekranga xalqalarni ko‘chirish bo‘yicha amallar ketma-ketligini chop etadi: