“Ma'lumotlar tuzilmasi va algoritmlar” fanidan

Agar faktorial funksiyasiga n>0 qiymat berilsa, quyidagi holat ro’y beradi: shart operatorining else shoxidagi qiymati (n qiymati) stekda eslab qolinadi. Noma’lumlarni hisoblash uchun shu funksiyaning o’zi «oldingi» qiymat (n-1 qiymati) bilan bilan chaqiriladi. O‘z navbatida, bu qiymat ham eslab qolinadi (stekka joylanadi) va yana funksiya chaqiriladi va hakoza. Funksiya n=0 qiymat bilan chaqirilganida if operatorining sharti ()!n rost bo‘ladi va «return 1;» amali bajarilib, ayni shu chaqirish bo‘yicha 1 qiymati qaytariladi, Shundan keyin «teskari» jarayon boshlanadi - stekda saqlangan qiymatlar ketma-ket olinadi va ko‘paytiriladi: oxirgi qiymat aniqlangandan keyin (1), u undan oldingi saqlangan qiymatga 1 qiymatiga ko‘paytirib F(1) qiymati hisoblanadi, bu qiymat 2 qiymatiga ko‘paytirish bilan F(2) topiladi va hakoza. Jarayon F(n) qiymatini hisoblashgacha «ko‘tarilib» boradi. Bu jarayonni, n=4 uchun faktorial hisoblash sxemasini 5.2-rasmda ko‘rish mumkin:

F(4)=4*F(3)

F(4)=4*F(3)

F(4)=4*F(3)

F(4)=4*F(3)

F(4)=4*6

F(3)=3*F(2)

F(3)=3*F(2)

F(3)=3*F(2)

F(3)=3*2

F(2)=2*F(1)

F(2)=2*F(1)

F(2)=2*1

F(1)=1*F(0)

F(1)=1*1

F(0)=1

5.2-rasm. 4! Hisoblash sxemasi

Rekursiv funksiyalarni to‘g‘ri amal qilishi uchun rekursiv chaqirishlarning to‘xtash sharti bo‘lishi kerak. Aks holda rekursiya to‘xtamasligi va o‘z navbatida funksiya ishi tugamasligi mumkin. Faktorial hisoblashida rekursiv tushishlarning to‘xtash sharti funksiya parametri n=0 bo‘lishidir (shart operatorining rost shoxi).

Har bir rekursiv murojaat qo‘shimcha xotira talab qiladi – funksiyalarning lokal obyektlari (o‘zgaruvchilari) uchun har bir murojaatda stekdan yangidan joy ajratiladi. Masalan, rekursiv funksiyaga 100 marta murojaat bo‘lsa, jami 100 lokal obyektlarning majmuasi uchun joy ajratiladi. Ayrim hollarda, juda ko‘p rekursiya bo‘lganda, stek o‘lchami cheklanganligi sababli (real rejimda 64Kb o‘lchamgacha) u to‘lib ketishi mumkin va bu holatda programma o‘z ishini «Stek to‘lib ketdi» xabari bilan to‘xtadi.

Quyida, rekursiya bilan samarali yechiladigan «Xanoy minorasi» masalasini ko‘raylik.

Masala. Uchta A, B, C qoziq va n-ta har xil o‘lchamli xalqalar mavjud. Xalqalarni o‘lchamlari o‘sish tartibida 1 dan n gacha tartiblangan. Boshda barcha xalqalar A qoziqqa 5.3a –rasmdagidek joylashtirilgan. A qoziqdagi barcha xalqalarni B qoziqqa yordamchi C qoziqdan foydalangan holda, quyidagi qoidalarga amal qilgan holda o‘tkazish talab etiladi: xalqalarni bittadan ko‘chirish kerak va katta o‘lchamli xalqani kichik o‘lchamli xalqa ustiga qo‘yish mumkin emas.
Amallar ketma-ketligini chop etadigan («Xalqa q dan r ga o‘tkazilsin» ko‘rinishida, bunda q va r - 5.3-rasmdagi A,B yoki C xalqalar). Berilgan n ta xalqa uchun masalani yechilsin.

Ko’rsatma : xalqalarni A dan B ga to‘g‘ri o‘tkazishda 5.3b –rasmlardagi holat yuzaga keladi, ya’ni n xalqani A dan B o‘tkazish masalan n-1 halqasini A dan C ga o‘tkazish, hamda bitta xalqani A dan B o’tkazish masalasiga keladi. Undan keyin C qoziqdagi n-1 xalqali A qoziq yordamida B qoziqqa o‘tkazish masalasi yuzaga keladi va hakoza.

Xalqalar soni 3 bo‘lganda (Xalqalar_Soni=3) programma ekranga halqalarni

ko‘chirish bo‘yicha amallar ketma-ketligini chop etadi:

Xalqa A dan B ga o’tkazilsin

Xalqa A dan C ga o’tkazilsin

Xalqa B dan C ga o’tkazilsin

Xalqa A dan B ga o’tkazilsin

Xalqa C dan A ga o’tkazilsin

Xalqa C dan B ga o’tkazilsin

Xalqa A dan B ga o’tkazilsin

Rekursiya chiroyli, ixcham ko‘ringani bilan xotirani tejash va hisoblash vaqtini qisqartirish nuqtai-nazaridan imkon qadar uni taticri hisoblash bilan almashtirilgani ma’qul. Masalan, x haqiqiy sonining n-darajasini hisoblashning quyidagi yechim varianti nisbatan kam resurs talab qiladi (n- butun ishorasiz son):

Lekin shunday masalalar borki, ularni yechishda rekursiya juda samarali, hattoki, yagona usuldir. Xususan, grammatik tahlil masalalarida rekursiya juda ham o‘ng‘ay hisoblandi.

Qayta yuklanuvchi funksiyalar: [3(72-73)] Ayrim algoritmlar berilganlarning har xil turdagi qiymatlari uchun qo‘llanishi mumkin. Masalan, ikkita sonning maksimumini topish algoritmida bu sonlar butun yoki haqiqiy turda bo‘lishi mumkin. Bunday hollarda bu algoritmlar amalga oshirilgan funksiyalar nomlari bir xil bo‘lgani ma’qul. Bir nechta funksiyani bir xil nomlash, lekin har xil turdagi parametrlar bilan ishlatish funksiyani qayta yuklash deyiladi.

Kompilyator parametrlar turiga va soniga qarab mos funksiyani chaqiradi. Bunday amalni «hal qilish amali» deyiladi va uning maqsadi parametrlarga ko‘ra aynan (nisbatan) to‘g‘ri keladigan funksiyani chaqirishdir. Agar bunday funksiya topilmasa kompilyator xatolik haqida xabar beradi. Funksiyani aniqlashda funksiya qaytaruvchi qiymat turining ahamiyati yo‘q.

Agar funksiya chaqirilishida argument turi uning prototipidagi xuddi shu o‘rindagi parametr turiga mos kelmasa, kompilyator uni parametr turiga keltirilishga harakat qiladi – bool va char turlarini int turiga, float turini double turiga va int turini double turiga o‘tkazishga.

Qayta yuklanuvchi funksiyalardan foydalanishda quyidagi qoidalarga rioya qilish kerak:

-qayta yuklanuvchi funksiyalar bitta ko‘rinish sohasida bo‘lishi kerak;

-qayta yuklanuvchi funksiyalarda kelishuv bo‘yicha parametrlar

ishlatilsa, bunday parametrlar barcha qayta yuklanuvchi funksiyalarda

ham ishlatilishi va ular bir xil qiymatga ega bo‘lish kerak;

-agar funksiyalar parametrlarining turi faqat “const” va ‘&’

belgilari bilan farq qiladigan bo‘lsa, bu funksiyalar qayta yuklanmaydi.

Adabiyotlar:

1. Харви Дейтел, Пол Дейтел. КАК ПРОГРАММИРОВАТЬ НА С++. М-2001, 1037c

2. Джефф Элджер. БИБЛИОТЕКА ПРОГРАММИСТА С++. М-2004, 300 с.

3. Madraximov Sh. F., Gaynazarov S. M. “C++ tilida programmalash asoslari” Toshkent-2009.-183 bet.

4. Елена Кондратюк. ТРЮКИ И ЭФФЕКТЫ С++. Москва – Санкт – Петербург -…-2006. 400 с.

5. Учебник по языку С++ в задачах и примерах. Электронный учебник.

6. www.ziyonet.uz

7.www.tuit.uz