Algoritmik tillar va dasturlash. Ma’ruza mashg’ulotlari uchun o’quv qo’llanma. X. E. Xolmirzayev, M. N. Ikromova, M. M. Bahromova Annotatsiya

12-Ma’ruza. Rekursiv va qayta yuklanuvchi metodlar

Reja:
1. Rekursiya va Rekursiv funksiyalar
2. Qayta yuklanuvchi metodlar.
Tayanch so’z va iboralar: Rekursiya tushunchasi, Rekursiv funksiyalar, to`g`ri rekursiya, yondosh rekursiya, qayta yuklanish


12.1. Rekursiya va Rekursiv funksiyalar. Rekursiya.
Rekursiya - funktsiyani o'z ichidan to'g'ridan-to'g'ri (oddiy rekursiya) yoki boshqa funktsiyalar (murakkab yoki bilvosita rekursiya) orqali chaqirish.
Rekursiv funksiyalar. Rekursiv funksiyalar o'zini chaqiradigan funksiyalardir. Masalan, faktorialni rekursiv funksiya sifatida hisoblashni aniqlaymiz:
Misol uchun, n formulasidan foydalanadigan faktoriy hisobni olaylik! = 1 * 2 *… * n. Ya'ni, aslida, sonning faktorialini topish uchun biz ushbu songacha bo'lgan barcha sonlarni ko'paytiramiz. Masalan, 4 sonining faktoriali 24 = 1 * 2 * 3 * 4, 5 sonining faktoriali esa 120 = 1 * 2 * 3 * 4 * 5.
int Factorial(int n)
{
if (n == 1) return 1;
return n * Factorial(n - 1);
}
Rekursiv funktsiyani yaratishda unda qandaydir asosiy variant bo'lishi kerak, undan funktsiyani hisoblash boshlanadi. Faktorial bo'lsa, bu 1 sonining faktorialidir, ya'ni 1. Barcha eksenel musbat sonlarning faktoriallari 1 sonining faktorialini hisoblashdan boshlanadi.
Dasturlash tili darajasida return operatori 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: barcha rekursiv chaqirishlar osti funktsiyalar ichida chaqirishi kerak, ular oxir-oqibat asosiy maqsadga yaqinlashadi:
return n * Factorial(n - 1);
Shunday qilib, funktsiyaga 1 ga teng bo'lmagan raqamni o'tkazishda qism funktsiyalarning keyingi rekursiv chaqiruvlari bilan har safar ularga bittadan kichik raqam uzatiladi. Va nihoyat, biz raqam 1 bo'ladigan va asosiy holat qo'llaniladigan holatga kelamiz. Bu rekursiv tushish deyiladi.
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) chaqirilganda nima sodir bo'lishini bosqichma-bosqich ko'rib chiqamiz.

1. Dastlab, 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 shunga ko'ra kod bajariladi.
return n * Factorial(n - 1);
Ya'ni, aslida bizda:
return 4 * Factorial(3);

2. Keyin 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. Keyin ifoda bajariladi:

Factorial(2)
Yana n 1 ga teng emas, shuning uchun kod bajariladi
return n * Factorial(n - 1);
Ya'ni, aslida:
return 2 * Factorial(1);

4. Keyin ifoda bajariladi:

Factorial(1);
Endi n 1 ga teng, shuning uchun kod bajariladi
if (n == 1) return 1;
Va 1 qaytadi.

Natijada, ifoda

Factorial(4);
Haqiqatda, u ichkariga tushadi
4 * 3 * 2 * Factorial(1)