Rekursiya - C++ da

Moodledan zerikkanda yozilgan maqolalar turkumidan...

Bu maqola uzundan-uzun bo'lib ketishi mumkin edi, agar rekursiyani boshidan tushuntirganimda, lekin o'zbekchada bu haqida juda chiroyli tushuntirilgan maqola bor: https://medium.com/@qudratxoja.musayev/agar-rekursiyani-5-yoshli-bolaga-tushuntirish-kerak-bolganda-2208aa75ac83

Maqolada rekursiya qanday ishlashi haqida ko'rib o'tamiz.

Eslatma: ushbu maqolani o'qishda sizdan ba'zi elementar bilimlar, ayniqsa funksiya haqidagi bilimlar kerak bo'ladi

Ko'pgina yuqori darajali dasturlash tillarida rekursiya ishlatilganda u aslida qanday ishlayotgani ko'rinmaydi, anglash ham birmuncha qiyin kechadi. Lekin mashina tillariga yaqin bo'lgan quyi darajali dasturlash tillarida(quyi deganda imkoniyati pastligi nazarda tutilmadi), masalan assemblerda rekursiya qanday bajarilishi stack orqali tushuntirilgani uchun uning asl mohiyati yaqqol ko'rinadi. Demak hozir stack haqida biroz gaplashib olsak.

Stack - biz data structures da ko'rgan abstract ma'lumot turi emas, balki xotiraning bir bo'lagi. U bilan ishlash uchun protsessorda maxsus buyruqlar mavjud. Statik xotiradan farqli o'laroq, qiymat uchun joy va u kiritilgandagina stackdan ajratiladi, ya'ni dinamik tarzda. Uning ishlash prinsipi LIFO(Last-In-First-Out - oxirgi kirgan birinchi chiqadi) qonuniyatiga asoslangan. Stekni biz bir tarafi berk quvurga o'xshatishimiz mumkin, unga biror narsa, masalan koptokchalarni solamiz, tabiiyki oxirgi kiritgan koptokchani birinchi bo'lib quvurdan chiqaramiz. Yoki dastlab kiritilgan koptokchani olish uchun ichidagi hamma koptokchalarni tashqariga chiqarib tashlashimiz kerak. Stack asosan keyinchalik kerak bo'ladigan vaqtinchalik qiymatlarni saqlashda ishlatiladi.

Stackni rekursiyaga qanday aloqasi bor?

Dastur kodida biror qatorga kelib funksiya chaqirilganda, funksiya ishini bajarib bo'lgach kod kelgan joyidan davom etib ketishi kerak. Bunda o'sha joyni xotiradagi manzilini eslab qolishimiz kerak. Funksiya chaqirganimizda stek xotirasiga quyidagi ketma-ketlikda qiymatlar kiritiladi:

Qaytuvchi qiymat uchun bo'sh joy;
Funksiyaga jo'natiladigan parametrlar;
Qaytish manzili;

So'ng funksiyaga murojaat qilinadi.

Ana endi funksiya stek ustida quyidagi amallarni bajaradi:

Kelgan stek manzilini stekka kiritadi;
Funksiya foydalanishi mumkin bo'lgan registrlar qiymatlarini kiritadi;
lokal o'zgaruvchilar uchun joy kiritadi;

Kerakli ish/hisob-kitoblar bajarilgach, stekdan quyidagi ketma-ketlikda qiymatlarni chiqarib oladi

Registrlarning avvalgi qiymatlarini tiklaydi;
avvalgi stek manzilini chiqarib, undan qaytish manzilini oladi, natijani stekka joylab, o'sha qaytish manziliga o'tadi.

Kod esa parametlarni chiqarib tashlab, qaytgan qiymatni oladi va sayohatini davom ettiradi.

Demak, ishni siz doim ko'rgan faktorialni hisoblash funksiyasidan boshlasak:

#include <iostream>

using namespace std;

unsigned int fakt(int son)

{

if(!son) return 1;

return son*fakt(son-1);

}

int main() {

cout<<"10! = "<<fakt(-10);

return 0;

}

Kodni yurgizganimizdagi ekranga chiqadigan natijasi:

10! = 3628800

Stek ko'rinishi taxminan shunaqa bo'ladi.

Funksiya o'ziga-o'zi murojaat qilganda har bir qiymat stekka joylanib, shu ketishda hisoblanib ketiladi.

Endi n-tartibli fibonachchi sonini topish kodini ko'ramiz. Quyida o'sha ko'pchilikka tanish kod:

#include <iostream>

#define ull unsigned long long

using namespace std;

ull fibo(int k)

{

return (k==1||k==2)? 1:fibo(k-1)+fibo(k-2);

}

int main() {

cout<<fibo(7);//1 1 2 3 5 8 13

return 0;

}

U qanday ketma-ketlikda o'z-o'zini chaqiryapti? Keling yaxshisi buni zanjirli tarzda tasvirlasak:

Elementlar soni 25 ta, ya'ni fibo(7)*2-1 ga teng. Lekin kattaroq tartibdagisini topmoqchi bo'lganimizda kod sekinroq ishlaydi. https://www.dcode.fr/fibonacci-numbers saytiga o'tib, 90-tartibdagi fibonachchi sonini ko'rib olamiz:

Yuqoridagi funksiyamizga 90-tartibdagi fibonachchi sonni topish uchun murojaat qilganimizda, u sekin ishlaydi, chunki o'z-o'ziga bo'lgan jami murojaatlar soni fibo(90)*2-1 ga teng(fibo(90) yuqoridagi rasmda). Keling endi kodni sal o'zgartiramiz, funksiya n-tartibdagi fibonachchi sonini topish uchun n-1 va n-2 -tartibdagilarni topmasdan, birato'la yo'l-yo'lakay hisoblab ketsin:

#include <iostream>

#define ull unsigned long long

using namespace std;

ull fibov2(int k, ull a = 1, ull b = 1)

{

return (k==1||k==2)? b:fibov2(k-1, b, a+b);

}

int main() {

cout<<fibov2(90);

return 0;

}

Va endi funksiyamiz vazifasini tezroq bajaradi.

Stek ham to'lib qolishi mumkinmi? Ha, bunday holatda dastur crash ga uchraydi(xatolik bo'lib, o'z ishini to'xtatadi). Masalan yuqoridagi faktorial funksiyamizga 1000000 qiymati berilganda shu holat kuzatiladi. Agar Stack overflow error bo'layotgan bo'lsa, yaxshisi yechimni while bilan qilgan ma'qul, har qanday rekursiv kodni while orqali sikl bilan hal qilsa bo'ladi.

Scala tilida tail recursion tushunchasi bor. Scala asoschisi Martin Oderskiy tail-recursion ni quyidagicha ta'riflagan(atamani tarjima qilolmadim, shuning uchun shundayligicha yozyapman):

"Oxirgi qiladigan ishlari - o'z-o'ziga murojaat qilish bo'lgan funksiyalar - tail-recursive funksiyalar deyiladi. Scala kompilyatori tail-recursion ni aniqlab, funksiya parametrlarini yangi qiymatlar bilan o'zgartirgach funksiya boshiga qaytadi..."

Manba: https://www.james-willett.com/scala-recursion/

Ushbu saytda Scala dasturlash tilida tail-recursion ga namuna ham keltirilgan:

def improvedFactorial(n: Int): BigInt = {

@tailrec

def factHelper(x: Int, accumulator: BigInt): BigInt =

if (x <= 1) accumulator

else factHelper(x-1, x * accumulator)

factHelper(n, 1)

}

println(improvedFactorial(5))

Odatdagi rekursiya hollarida, biz hisob kitoblarni barcha qiymatlar qaytmagunicha bajarmaymiz. Yuqoridagi faktorialni hisoblash funksiyamiz bunga misol bo'la oladi.

Tail-recursion da esa, biz avval hisob-kitoblarni bajarib, so'ngra natijalarni funksiyani o'ziga berish orqali rekursiya hosil qilamiz. Demak, yuqoridagi fibov2 funksiyamizni tail-recursive desak bo'ladi.

Agar siz ishda kod hajmiga e'tibor qaratsangiz, rekursiyadan foydalanishingiz mumkin. Agar fokusni time complexity ga qaratsangiz, u holda sikldan foydalanish yaxshi yechim bo'lishi mumkin.

Yuqoridagi hollar rekursiya uchun ayrimlari edi, rekursiya yoki sikldan foydalanishni vaziyatga qarab o'zingiz tanlashingiz kerak bo'ladi.

Maqola bo'yicha fikr, savol, qo'shimcha, tanqidlar bo'lsa yuqorida ko'rsatilgan muallifga murojaat qiling. Maqola texnik jihatdan chala va kamchiliklari bo'lishi mumkin, u hali to'ldirilishi kerak. Mavzu bo'yicha shu manba bilan kifoyalanmasdan, yana izlanishingizni so'rab qolardim.

To'ldiruvchi(lar): Mumtozbekov♏️

Foydalanilgan manbalar:

Rekursiya - C++ da

Report Page