6-amaliy mashg'ulot Rekursiv Funksiya

6-amaliy mashg'ulot
Rekursiv Funksiya
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 ning faktoriali 24 = 1 * 2 * 3 * 4, 5 ning faktoriali esa 120 = 1 * 2 * 3 * 4 * 5 ga teng.

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 variantni 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 = {factorial4}");

Console.WriteLine($"Факториал числа 5 = {factorial5}");
Console.WriteLine($"Факториал числа 6 = {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 n 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);
2.Quyidagi ifoda bajariladi:
Factorial(3)
Yana n 1 ga teng emas, shuning uchun kod bajariladi
return n * Factorial(n - 1);
Ya'ni, aslida:
return 3 * Factorial(2);
3.Quyidagi ifoda bajariladi:
Factorial(2)
Опять же n не равно 1, поэтому выполняется код
return n * Factorial(n - 1);
Ya'ni, aslida:
return 2 * Factorial(1);
4.Quyidagi ifoda bajariladi:
Factorial(1)
Endi n 1 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 число Фибоначчи = {fib4}");

Console.WriteLine($"5 число Фибоначчи = {fib5}");
Console.WriteLine($"6 число Фибоначчи = {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 tsikllar
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.