Rekursiya — hayotdan misol va undan unumli foydalanish

Rekursiya — funksiya(protsedura)ni shu funksiyani ichida chaqirilishi deb qarasak eng tushunarli ko’rinish bo’ladi

Dasturchilar orasida shunday gap bor: «Rekursiyani bilish uchun, avval uni bilish kerak». Rekursiv gap-a?

Rekursiya bajarilishi uchun ikkita narsa bolishi kerak
1. O’zini chaqirish
2. To’xtash chegarasi

Hech oyingiz sizga uyga kirda karobkani ichidan biror nimani olib chiq deganlami? Siz esa karobkalani kovlab-kovlab 1 soatda topgansiz/yoki umuman topolmagansiz.
Chunki siz korobkani ko’rib chiqish ketma-ketligini to’g’ri qo’ymagansiz

Masala: korobkalar ichma-ich ixtiyoriy joylashtirilgan, qaysidir korobka ichida kalit bor. Siz kalitni topish dasturini tuzing

Rekursiyaga qoyish uchun ushbu ikki shart yozib olamiz:
1. Ishlash sharti: korobka ichida korobka chiqsa, uni ochib ko’r
2. To’xtash sharti: korobka ichidan kalit chiqsa to’xta

Rekursiv funksiyaning to’xtash chegarasi bo’lmasa esa, amallar cheksiz bajarilaveradi, oqibatda crash beradi, yoki dastur osilib qoladi. Xo’sh nega?

Funksiya ishga tushganda keyingi chaqirilayotgan funksiya STACKka qo’shib borilaveradi. Rekursiv funksiya ishlaganda o’zi o’zi chaqirishini ayttim, aynan chaqiruvchi funksiya esa chaqirilgan funksiyani natijasini kutib turadi, u esa o’zi chaqirgan funksiya natijasiga bog’liq bo’ladi …. va hokazo toki to’xtash nuqtasidagi funksiyaga borgunicha. Oxirgi nuqtadagi funksiya ishlaganda esa, stackdan chiqib ketib undan oldingisi bajarilib, undan oldingisiga javob yetib boradi … va hokazo eng birinchi chaqirilgan funksiya eng oxirida yopiladi.

Ushbu stack to’lib qolsa yoki to’xtash chegasi noto’g’ri qo’yilishi oqibatida Stack Overflow error olasiz.

Keling buni printFun funksiya misolida ko’ramiz

void printFun(int test) //C++ 
{ 
    if (test 
int main() 
{ 
    int test = 3; 
    printFun(test); 
} 

Quyidagi Rasmda e’tibor bering printFun funksiyasi 3 argumenti bilan chaqirilganda to 1 ga bormagunga qadar 3, 2, bilan chaqirilgan funksiyalar kutib turibdi. Va nihoyat 1 bilan chaqirilgan element yopilgach, teskari ketma-ketlikda 2, 3 bilan chaqirilgan funksiyalar ham yopildi.

NATIJA:
3 2 1 1 2 3

Ko’p rekursiv masalalarni oddiy siklda ham bajarsa bo’ladi degan fikr bor, buni keyingi postlarda ko’ramiz

—

Yana bir misol N sonining Faktorialini aniqlash:

def fact(x): #python 
    if x == 1: 
        return 1 
    else: 
        return x*fact(x-1) 

Bu yerda ikkita shart sifatida:
1. Rekursiya sharti: o’zidan kichik sonni chaqirish
2. to’xtash sharti: 1 ga borganda to’xtash

Ishlash stacki esa tepadagi rasmda keltirilgandek.
fact(3) chaqirilganda fact(3)->fact(2) ni chaqiradi va natijasini kutib ishini tagatmay turadi, xuddi shunday fact(2) fact(1) chaqirdi, fact(1) yopilgacha esa stack teskarisiga bo’shab boradi

Rekursiyaning boshqacha ko’rinishlari ham bor, keyinroq «Bo’lib ol va boshqar» prinsipiga asosan ishlaydigan rekursiyalarni ham ko’ramiz

Shu va shunga o’xshagan algoritmlar haqida o’z blogim(t.me/bars222)da yozib borishni boshladim, kuzatib boring, fikr va savollaringni eshitishga welcome