9-mavzu. Chiziqsiz ma’lumotlar tuzilmasi. Daraxtsimon maʻlumotlar tuzilmalari. Binar va ko‘ptarmoqli daraxtlar. Taʻriflar va xususiyatlar. Daraxtlarni binar ko‘rinishga keltirish algoritmi. Rekursiya va ularni dasturlashda ishlatish

Dumli Rekursiya

Barcha rekursiyalar uchun aniqlanayotgan to’plam yoki funksiyaning ma’lumotlari o’zida jamlanishi kerak. Bunaqa ma’lumotlarning juda ko’p turlari joriy etilishi mumkin. Bu ma’lumotlardan ko’p marotaba, turli yo’sinlarda foydalanish mumkin. Rekursiyaning turli darajalari mavjud bo’lib, ularning murakkablik darajalari ham turlicha. Quyida, bunday turlarning ba’zilari muhokama qilinadi. Ularning oddiysi – dumli rekursiya. Dumli rekursiya faqatgina bitta rekursiv murojaatni funksiya oxirida qo’llash orqali xarakterlanadi.Boshqacha qilib aytganda, murojaat bo’lganda, funksiya orqali amalga oshirilishi kerak bo’lgan birorta so’z qolmaydi; rekursiv murojaat eng so’nggi emas, unda erta bo’lmagan, to’g’ridan-to’g’ri yoki o’zlashtirma turdagilari ham mavjud. Misol uchun, tail() funksiyasi quyidagicha aniqlanadi:

void tail(int i){

if(i>0){cout<

tail(i-1);}

}

tail (dumli ) rekursiya li funksiyaga misol, bundaki nonTail funksiyasi quyidagicha izohlanadi:

void nonTail(int i) {

if (i > 0) {

nonTail(i-1);

cout << i << '';

nonTail(i-1);

}

}

Dumli rekursiya qurilishi oddiygina va kimdir tomonidan osonlikcha joylashtirilishi mumkin. Buni quyidagi I o’zgaruvchining qiymatini unga bo’lgan rekursiv murojaatlar darajasi orqali kamaytirib borish misolida ko’rish mumkin. Bunda, tail() iterativ funksiya orqali ifodalanishi mumkin:

void iterativeEquivalentOfTail(int i) {

for ( ; i > 0; i--)

cout << i << '';

}

Dumli rekursiyani iteratsiya orqali foydalanishning afzalligi mavjudmi? C++ kabi tillar uchun, solishtiriladigan hech qanday foydali tomonlari bo’lmasligi mumkin, lekin Prolog kabi tillarda bu juda kata ahamiyatga ega bo’ladi. If goto bilan birga qo’llaniladigan hollarda dumli rekursiyadan foydalanmaslik ma’qul.

Dumsiz Rekursiya

Rekursiyalarda mavjud boshqa muammo bu qiymat kiritish qatorlarini teskari tartibda chiqarib berishdir. Quyida oddiy rekursiya qo’llanilishi berilgan:

/* 200 */ void reverse() {

char ch;

/* 201 */ cin.get(ch);

/* 202 */ if (ch != '\n') {

/* 203 */ reverse();

/* 204 */ cout.put(ch);

}

}

Aldab qo’yadigan joyi qayerda? Bu funksiya nimadir bajaradigandek tuyulmaydi hech. Lekin bu rekursiyaning ahamiyatliligi bilan main() ning reverse() ko’rinishidagi turi va kiritish “ABC” qatordir. Avvalo, buni faollashtirish yacheykalar orqali ch o’zgaruvchi uchun amalga oshiriladi va adresni qaytaradi. Funksiya nomi yonida void ishlatilsa funksiya hech qanaqa qiymat qaytarmaydi, shuning uchun, natija yacheykasi uchun ham hech qanaqa almashtirishlar kerak emas. get() funksiyasi birinchi belgida “A” ni o’qiydi. Chizma 5.3a birinchi marotaba reverse() o’z-o’ziga murojaat qilgandagi ishga tushirish vaqt stekidagi holat ko’rsatilgan.

Chizma 5.3 reverse() amalga oshirilgandagi ishga tushirish vaqt stekidagi o’zgarishlar.

Ikkinchi belgi o’qib olindi va so’nggi belgi ekanligiga tekshiriladi va unday bo’lmasa reverse()ga qayta murojaat qilinadi. Lekin har qanaqa holatda ham , ch ning qiymati qaytarilgan qiymat bo’yicha ishga tushirish vaqti stekga joylashtiriladi. Reverse 3-marotaba chqirilmasidan oldin, stekda ikki yoki undan ortiq belgilar mavjud( chizma 5.3b ) So’nggi belgiga yetmaguncha funksiyaga qayta-qayta murojaatlar bo’laveradi. Bizning misolimizda, reverse()ga 4 marta murojaat etilgan va so’nggi murojaatgacha bo’lgan o’zgarishlar va jarayonlar 5.3d da ko’rsatilgan. To’rtinchi murojaatda, get() so’nggi belgini topadi va reverse() boshqa ishlamaydi. Sistema faollashtirish natijalaridan uning adresii qaytaradi va SPni orttirish orqali aniq bitlar yordamida bu rekordni yaroqsiz qilib tashlab yuboradi. Bajarilgan amallarni chop etish uchun 204 qatordan boshlanadi.Uchinchi murojaat faollik rekordi faol bo’lganda, ch ning qiymati, “C” harfi, birinchi belgi sifatida ekranga chiqariladi. Va nihoyat, reverse() ning birinchi murojaatining faollik rekordiga yetib kelindi. Keyin “A” chiqariladi va ekranda ko’rilishi mumkin bo’lgan qator “CBA” ko’rinishida bo’ladi. Birinchi murojaat butunlay yakunlanadi va dastur ijrosi main() da bo’ladi.

Bir xil funksiya uchun rekursiv hamda rekursiv bo’lmagan ijrolarini taqqoslang:

void simpleIterativeReverse() {

char stack[80];

register int top = 0;

cin.getline(stack,80);

for (top = strlen(stack) - 1; top >= 0; cout.put(stack[top--]));

}

Funksiya ancha qisqa va balkim ozroq tushunarsiz. Xo’sh, unda farq nimada? Qisqalik va soddalikning sababi biz belgilardan tashkil topgan satr yoki massivni teskarisiga o’zgartirmoqchi bo’lganimizda ekanligini yodingizda saqlang.

Bu shuni anglatadiki, strlen() va getline() ga o’xshagan funksiyalardan C++ standard kutubxonasidan foydalanishimiz mumkin. Agar bizda bunaqa funksiyalar mavjud bo’lmasa, unda bizning iterative funksiyamiz boshqacharoq bajarilishi lozim:

void iterativeReverse() {

char stack[80];

register int top = 0;

cin.get(stack[top]);

while(stack[top]!='\n')

cin.get(stack[++top]);

for (top -= 2; top >= 0; cout.put(stack[top--]));

}

While ga tegishli getline() va yuqori qiymatlarning avtoinkrementi strlen() o’rnida kelgan. For esa odatdagidek xilda. Bu tahlil albatta, aniq teoretik emas, chunki butun sonlarni o’z ichiga oluvchi kiritish qatorini teskarisiga aylantirish stekning ma’lumotlar tipini char dan int ga o’zgartirgandan keyin iterativeReverse() dek bir xil bajariladi.

Massiv uchun stekda foydalanilgan o’zgaruvchi nomi tasodifiy emasligini yodda tuting. Biz, shunchaki, Sistema tomonidan shubhasiz bajarilganlarni oydinlashtiramiz. Bizning stek amalga oshirish vaqti stekidan ko’proq vaqt talab etadi. Bu muhim, chunki birgina oddiy murojaatlar bunda dumli rekursiyada yetarli bo’lganidek yetarli emas. Rekersiv versiyadagi put() ham bunda hisobga olinishi zarur. iterativeReverse() funksiyasi uchun stek o’zgaruvchisi lokal ekanliginiham yodda saqlang. Shunday bo’lsada, agar global tarzda st obyekti yaratilishi talab etilsa, unda buning amalda qo’llanilishini quyidagicha yozish mumkin bo’ladi:

void nonRecursiveReverse() {

int ch;

cin.get(ch);

while (ch != '\n') {

st.push(ch);

cin.get(ch);

}

while (!st.empty())

cout.put(st.pop());

}

stek st ning funksiyadan tashqardagi e’loni bilan. iterativeReverse() ni nonRecursiveReverse()ga taqqoslagandan keyin , biz shunday xulosa qilishimiz mumkinki, birinchi versiya yaxshiroq, chunki, u tezroq ishlaydi va hech qanaqa funksiya murojaatlari yo’q va funksiya o’z-o’zini qoniqtiradi, lekin nonRecursiveReverse() esa har bir iteratsiyada kamida bitta murojaatdan foydalanadi, dastur ishlashi ham sekin. Funksiya rekursiv likdan iteraktivversiyaga o’zgartirilganda , dastur aniqligiga zarar yetishi mumkin va dastur kodining qisqaligi yo’qolishi mumkin. C++dagi rekursiv funksiyalarning iteraktiv versiyalari boshqa dasturlash tillaridagi kabi uzun emas, shu sababli dastur qisqaligi ahamiyatga molik bo’lmasligi mumkin.

Xulosa o’rnida, von Kochning qor uchquni qurilishini ko’rib chiqamiz. Egri chiziqlarga1904da shved matematigi Helge von Koch tomonidan ishlab chiqilgan noaniq uzunlik va atrofini qurshab olgan aniq maydonga ega bo’lgan davomiy hamda differensiallanuvchi funksiyani misol qilishimiz mumkin. Bunday egri chiziqlarga qor uchqunlarning noaniq ketma-ketligiligining limiti sifatida qarash mumkin, bularning birinchi uchtasi Chizma 5.4da namoyish etilgan. Haqiqiy qor uchqunlarida bo’lganidek, bularning ikkitasi oltita gultojbargli naqshlarga ega, lekin uning algoritmini yengillashtiradigan bo’lsak, u uchta oddiy egri chiziqning birlashmasi sifatida qaraladi. Shunday egri chiziqlarning bittasi quyidagicha chiziladi:

1. Interval qismini uchta bir xil bo’laklarga bo’ling.

2. Tomonning uchdan bir qismini burchak bo’yicha harakatlantiring.

3. O’ngga 60°ga buring (yoki –60°) va tomonning uchdan bir qismini yo’naltiring.

4. Chapga 120°ga buring va qolgan uch qismida ham davom ettiring.

5. O’ngga 60°ga buring va tomon bo’ylab yana chiziq chizing.

Bu besh qadamlarning natijasi Chizma 5.5da birlashtirilgan. Kompyuter grafikasi bizni juda uzoq masofalarga cho’zilishga aslo hojat qoldirmaydi, chunki agar chiziqlar piksellarning diametridan kichikroq bo’lsa, biz ekranda faqatgina bir nuqta sifatida ko’ramiz, xolos.