Mavzu: C# dasturlash asoslari. Reja: Kirish Asosiy qism

Rekursiv funktsiyalar.

C# Keling, rekursiv funktsiyalarga alohida to'xtalib o'tamiz. Rekursiv funktsiya - bu funktsiya o'zini chaqiradigan konstruktsiyadir.
Rekursiv faktorial funksiya
Masalan, n formulasidan foydalaniladigan faktorial hisobni olaylik! = 1 * 2 * ... * n . Ya'ni, aslida, sonning faktorialini topish uchun barcha sonlarni shu songacha ko'paytiramiz. Masalan, 4 24 = 1 * 2 * 3 * 4ning faktoriali , 5 ning faktoriali esa 120 = 1 * 2 * 3 * 4 * 5.
Faktorialni topish usulini belgilaymiz:
int Factorial(int n)
{
if (n == 1) return 1;
return n * Factorial(n - 1);
}
Rekursiv funktsiyani yaratishda u, albatta , funktsiyani hisoblash boshlanadigan ba'zi bir asosiy versiyani o'z ichiga olishi kerak. Faktorial bo'lsa, bu 1 raqamining faktorialidir, ya'ni 1. Boshqa barcha ijobiy sonlarning faktoriallari 1 bo'lgan 1 raqamining faktorialini hisoblashdan boshlanadi.
Dasturlash tili darajasida return iborasi asosiy holatni qaytarish uchun ishlatiladi :
if (n == 1) return 1;
Ya'ni, agar kirish raqami 1 bo'lsa, u holda 1 qaytariladi.
Rekursiv funktsiyalarning yana bir xususiyati shundaki, barcha rekursiv qo'ng'iroqlar oxir-oqibat asosiy holatga yaqinlashadigan pastki funktsiyalarga murojaat qilishi kerak:
return n * Factorial(n - 1);
Shunday qilib, 1 ga teng bo'lmagan raqamni funktsiyaga o'tkazishda, pastki funktsiyalarga keyingi rekursiv qo'ng'iroqlar bilan, har safar ularga bittadan kichik raqam uzatiladi. Va oxirida biz raqam 1 ga teng bo'ladigan holatga erishamiz va asosiy holat ishlatiladi. Bu rekursiv tushish deb ataladi.
Keling, ushbu funktsiyadan foydalanamiz:
int Factorial(int n)
{
if (n == 1) return 1;
return n * Factorial(n - 1);
}
int factorial4 = Factorial(4); // 24
int factorial5 = Factorial(5); // 120
int factorial6 = Factorial(6); // 720
Console.WriteLine($"4 faktorial = {factorial4}");
Console.WriteLine($"5 faktorial = {factorial5}");
Console.WriteLine($"6 faktorial = {factorial6}");
Faktorial(4) chaqirilsa nima bo'lishini bosqichma-bosqich ko'rib chiqamiz.
Birinchidan, u raqam birga teng yoki yo'qligini tekshiradi:
if (n == 1) return 1;
Lekin boshida nu 4 ga teng, shuning uchun bu shart noto'g'ri va kod shunga mos ravishda bajariladi
return n * Factorial(n - 1);
Shunday qilib, aslida bizda:
return 4 * Factorial(3);
Quyidagi ifoda bajariladi:
Factorial(3)
Shunga qaramay, n1 ga teng emas, shuning uchun kod bajariladi
return n * Factorial(n - 1);
Ya'ni, aslida:
return 3 * Factorial(2);
Quyidagi ifoda bajariladi:
Factorial(2)
Shunga qaramay, n1 ga teng emas, shuning uchun kod bajariladi
return n * Factorial(n - 1);
Ya'ni, aslida:
return 2 * Factorial(1);
Quyidagi ifoda bajariladi:
Factorial(1)
Endi n1 ga teng, shuning uchun kod bajariladi
if (n == 1) return 1;
Va u 1 ni qaytaradi.
Natijada, ifoda
Factorial(4)
Aslida, u aylanadi
4 * 3 * 2 * Factorial(1)
Rekursiv Fibonachchi funktsiyasi
Rekursiv funktsiyaning yana bir keng tarqalgan misoli Fibonachchi raqamlarini hisoblaydigan funktsiyadir. Fibonachchi ketma-ketligining n-chi a’zosi f(n)=f(n-1) + f(n-2), f(0)=0 va f(1)=1 formula bilan aniqlanadi. 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, .... ushbu ketma-ketlikning raqamlarini aniqlaymiz, 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 - fibonachi soni= {fib4}");
Console.WriteLine($"5 - fibonachi soni= {fib5}");
Console.WriteLine($"6 - fibonachi soni= {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, ifoda natijasi qaytariladi.Fibonachi(n - 1) + Fibonachi(n - 2);
Bular rekursiv funktsiyalarning eng oddiy misollari bo'lib, ular sizga rekursiya qanday ishlashi haqida tushuncha berish uchun mo'ljallangan. Shu bilan birga, ikkala funksiya uchun ham rekursiyalar o'rniga siklik konstruktsiyalardan foydalanish mumkin. Va umuman olganda, tsiklga asoslangan alternativalar rekursiyaga qaraganda tezroq va samaraliroq. Masalan, halqalar 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, rekursiya ba'zi holatlarda, masalan, kataloglar va fayllar daraxti kabi turli xil daraxt ko'rinishlarini kesib o'tishda oqlangan yechimni ta'minlaydi.

3.