u qo‘llanmada ko‘rib chiqilgan Ijrochilardan faqat Kamayti- ruvchi va Robotda shart bor. Demak, faqat shu ikki Ijrochi uchun rekursiv protseduralarni yozish ma’noga ega.
Bizning mulohazalarimizdan shunday xulosaga kelish mumkin:
B Rekursiv protseduralarni yozganda rekursiv chaqirish yuzaga
kelmaydigan shart ko‘rsatilishi kerak.
u juda kerakli xulosa! Shuning uchun ham avvalgi bo‘limda algoritm namunalarini keltirganimizda, rekursiv protsedu- ralarning shunday shartlarini va zaruriy amallarining tavsifini yozishdan boshlaganmiz. masala
Quyidagimasalalardarekursivchaqirishyuzagakelmaydiganshartlarnihamdabuholdaqandayamallarbajarilishizarurliginiko‘rsating: kamaytiruvchi tomonidan ixtiyoriy sondan 0 ni hosil qilish;
robot o‘tish joyi bo‘lgan gorizontal devor tagida turibdi. O‘tish joyi chapda yoki o‘ngdaligi noma’lum. O‘tish joyini toping; robot o‘tish joyi bo‘lgan gorizontal devor tagida turibdi. O‘tish joyi Robotdan chapda. Robot undan o‘tib boshlang‘ich holati ustiga borib turishi kerak;
robotdan yuqorida bo‘yalgan katak bor. Robot maydonida devorlar yo‘q. Robotni bo‘yalgan katakdan yuqoridagi shunday katakka olib kelingki, Robot bilan bo‘yalgan katak orasidagimasofa Robotning boshlang‘ich holatidagi katak bilan bo‘yalgan katak orasidagi masofadan uch marta katta bo‘lsin.
Qachon rekursiyasiz ishlash mumkin
Ko‘rinishidan sodda ko‘ringani bilan rekursiya bilan ishlash ancha murakkab. Haqiqatan, Dehqon, Suvchi, Chigirtka uchun birinchi algoritmlarimizni eslang. Ularning to‘g‘riligini tekshirish juda oson edi. Biz Ijrochining har bir ko‘rsatmadan keyingi holatini kuzatib turar va barcha ko‘rsatmalar bajarilgandan keyin uning holati masala shartini qanoatlantirishiga ishonch hosil qilar edik.
Takrorlash tuzilmasining kiritilishi tekshirishni unchalik murak- kablashtirmadi. Ijrochining harakati avvalgidek uning holatiga bog‘liq emasdi. Yagona qo‘shimcha qiyinchilik shundan iborat ediki, juda qisqa yozuvli algoritm bajarilishi natijasida Ijrochi juda ko‘p amallarni bajarishi kerak bo‘lardi.
Shart kiritilishi algoritmning to‘g‘riligini tekshirishda bosh- qacha aks etadi. Endi Ijrochining bajarishi kerak bo‘lgan ko‘rsatmalar ketma-ketligi Ijrochining holatiga bog‘liq bo‘ldi — 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 qo‘llash yana tekshirish qiyinchiligini chuqur- lashtiradi. Haqiqatan, biz endi qaysi ko‘rsatma bajarilayotganini kuzatibgina qolmasdan, bu ko‘rsatma qayerdan paydo bo‘lganini ham bilishimiz kerak.
Aytaylik, 7.1-masala yechimidagi simmetriya rekursiyasi ishini tekshirayotib, navbatdagi chapga ko‘rsatmasi rekursiv protsedurani uchinchi yoki beshinchi chaqirishda paydo bo‘lgani va hokazoni yodda saqlashimiz kerak. Yana agar rekursiv protseduralar algoritmda ko‘p bo‘lib, bir-birini chaqirsa-chi?
Tekshirish qiyinligi — bu rekursiyalardan foydalanishdan tiyilishning sabablaridan faqat bittasidir. Boshqa sabablar ham 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?
masala
Kamaytiruvchi uchun ixtiyoriy sonni eng kam qadamda 0 ga olib keluvchi rekursiv protsedura tuzing. Quyidagi sonlar uchun protsedurangiz bajarilayotgandagi Kamaytiruvchining ko‘rsatmalar ketma-ketligini yozing: 5;
9;
d) 14.
Kataklarni bo‘yab, Robot bilan ishlaganda rekursiyadan qutulish mumkin. Bunda bo‘yalgan kataklar xotira vazifasini o‘taydi. Bu holda bo‘yalgan sharti Robot bu katakdan o‘tgan yoki o‘tmaganini bilish uchun imkon beradi.
masala
Robot devordan yuqorida qandaydir masofa uzoqlikda turibdi. Quyidagi imkoniyatlarda Robotni devorgacha olib borib joyiga qaytarib olib keluvchi protsedura tuzing: rekursiyani ishlatish mumkin;
bo‘yash mumkin, rekursiyani ishlatish mumkin emas.
Bu masalalardan birortasi ham sizga qiyinchilik keltirib
Ba’zan protseduralarni yozganda uning o‘zini o‘zining ichida boshqa protsedura orqali chaqirgan qulay. To‘g‘ri to‘rtburchakni bo‘yash masalasining rekursiv yechimini qaraymiz.
masala
Robot devorlar bilan o‘ralgan to‘g‘ri to‘rtburchakning chap quyi burchagida turibdi. To‘g‘ri to‘rtburchakning ichida devorlar yo‘q. To‘g‘ri to‘rtburchakning barcha kataklarini bo‘yash algoritmini tuzing.
Yechim. Ikkita rekursiv protsedurani qo‘llaydigan bo‘yash algoritmini yozamiz:
TOKI quyi bo‘sh BAJAR quyiga TAMOM AGAR o‘ng bo‘sh U HOLDA o‘ngga
to‘g‘ri to‘rtburchakni bo‘ya TAMOM TAMOM
Endi algoritm bitta ko‘rsatmadan iborat bo‘ladi.
to‘g‘ri to‘rtburchakni bo‘ya
Bizning yechimimizda to‘g‘ri to‘rtburchakni bo‘ya protsedurasi yo‘lakni bo‘ya va qayt protsedurasini chaqiradi. O‘z navbatida, yo‘lakni bo‘ya va qayt protsedurasi to‘g‘ri to‘rtburchakni bo‘ya protsedurasini chaqiradi. Shunday qilib, to‘g‘ri to‘rtburchakni bo‘ya protsedurasi o‘zini-o‘zi oraliq yo‘lakni bo‘ya va qayt protsedurasi orqali, yo‘lakni bo‘ya va qayt protsedurasi o‘zini o‘zi oraliq to‘g‘ri to‘rtburchakni bo‘ya protsedurasi orqali chaqiradi.
Bu holda ikkala protsedurani rekursiv deb hisoblaymiz va ular bilan oddiy protsedura kabi muomala qilamiz.
