|
Sharti yo'q Ijrochilar uchun rekursiv protseduralarni qoMlamang!
Bu qoMlanmada ko‘rib chiqilgan Ijrochilardan faqat Kamayti- ruvchi va Robotda shart bor. Demak, faqat shu ikki Ijrochi uchun rekursiv protseduralami yozish ma'noga ega.
Bizning mulohazalarimizdan shunday xulosaga kelish mumkin;
Rekursiv protseduralarni yozganda rekursiv chaqirish yuzaga kelmaydigan shart ko‘rsatilishi kerak.
alg Bu juda kerakli xulosa! Shuningiuchun ham awalgi bo‘limda ral oritm namunalarini l keltirgan mizda, rekursivn protsedu- arning shunday shart arini va zaruriy amallarini g tavsifini
yozishdan boshlaganmiz.
7.5-masala
shaQuyidagi masalalarda rekursiv chaqirish yuzaga kelmaydigan
rtlarni hamda bu holda qanday amallar bajarilishi zarurltgini
ko‘rsating:
qilia) ; kamaytiruvchi tomonidan ixtiyoriy sondan 0 ni hosil
sh
0 ‘tb) robot o‘tish joyi bo'lgan gorizontal devor tagida turibdi.
ish joyi chapda yoki o‘ngdaligi noma'lum. O'tish joyini
toping;
joyid) robot o'tish joyi bo'lgan gorizontal devortagida turibdi. O'tish
bo Robotdan chapda. Robot undan o‘tib boshlang'ich holati ustiga
rib turishi kerak;
de e) robotdan yuqorida bo'yalgan katak bor. Robot maydonida
kavorlar yo‘q. Robotni bo'yalgan katakdan yuqoridagi shunday
takka olib kelingki, Robot bilan bo'yalgan katak orasidagi
134
masofa Robotning boshlang‘ich holatidagi katak bilan bo‘yalgan katak orasidagi masofadan uch marta katta boMsin.
Qachon rekursiyasiz ishlash mumkin
ancKo'rinishidan sodda ko'ringani bilan rekursiya bilan ishlash biriha murakkab. Haqiqatan, Dehqon, Suvchi, Chigirtka uchun jud nchi algoritmlarimizni eslang. Ularning to‘g‘riligini tekshirish ho at oson edi. Biz r[jrochining har bir ko‘rsatmadan akeyingi unla ini kuzatib tura va barcha ko'rsatmalar bajarilgand n keyin qi ing holati masala shartini qanoatlantirishiga ishonch hosil
lar edik.
Takrorlash tuzilmasining kiritilishi tekshirishni unchalik murak-
kablashtirmadi. ljrochining harakati awalgidek uning holatiga
bog‘liq emasdi. Yagona qo‘shimcha qiyinchilik shundan iborat
ediki, juda qisqa yozuvli algoritm bajarilishi natijasida Ijrochi juda ko‘p amallami bajarishi kerak boMardi.
qa Shartkkiritilishi algoritmning to‘g‘riligini tekshirishda bosh-
k chat a sa etadi. Endii Ijrochining bajarishia kerak i bo‘lgan
o'rsa mal r ketma-ketl gi ljrochining holatig bogM q boMdi
— ish boshida Kamaytiruvchi ekranida qanday son aks etib turardi, Robot maydonida devorlar qanday joylashgan, Robot maydonining qaysi kataklari bo'yalgan.
Algoritmning oddiygina bajarilishi va to‘g‘ri natijaning olinishi algoritm to‘g‘ri ekanligiga ishontira olmaydi. Algoritm biz tekshira olgan yoki tekshirishni xohlagan hollardagina emas, balki ixtiyoriy holda ham to‘g‘ri ishlashiga ishonch hosil qilishimiz kerak. Albatta, ishonch hosil qilishning eng yaxshi usuli — bu algoritm ishining to'g'riligini isbotlashdir.
Rekursiyani qoMlash yana tekshirish qiyinchiligini chuqur- lashtiradi. Haqiqatan, biz endi qaysi koTsatma bajarilayotganini kuzatibgina qolmasdan, bu ko‘rsatma qayerdan paydo boMganini ham bilishimiz kerak.
Aytaylik, 7.1-masala yechimidagi simmetriya rekursiyasi ishini tekshirayotib, navbatdagi chapga koTsatmasi rekursiv protsedurani uchinchi yoki beshinchi chaqirishda paydo boMgani va hokazoni yodda saqlashimiz kerak. Yana agar rekursiv protseduralar algoritmda ko‘p boMib, bir-birini chaqirsa-chi?
Tekshirish qiyinligi — bu rekursiyalardan foydalanishdan
tiyilishning sabablaridan faqat bittasidir. Boshqa sabablar ham
135
bor: rekursiyali dasturlar rekursiyasiz dasturlarga nisbatan kom- pyuterda bajarayotganda sekin ishlaydi va xotiradan ko‘p joy talab qiladi; rekursiyali dasturlarni rekursiyasiz dasturlarga almashtirayotganda masalaga boshqa tomondan qarashga yor- dam beruvchi ajoyib fikrlar paydo bo'lishi mumkin. Shu sababli, masalaning rekursiv yechimini topgach, yana o‘ylab ko‘ring: rekursiyasiz ishlash mumkin emasmikan?
7.6- masala
ol Kamaytiruvchi uchun ixtiyoriy sonni eng kam qadamda Oga
ib keluvchi rekursiv protsedura tuzing. Quyidagi sonlar uchun
protsedurangiz bajarilayotgandagi Kamaytiruvchining ko‘rsatmalar ketma-ketligini yozing:
Do'stlaringiz bilan baham: | 
