Algoritmlash p65. p65

Qachon  rekursiyasiz  ishlash  mumkin
K o ‘rinishidan  sodda  ko ‘ringani  bilan  rekursiya  bilan  ishlash 
ancha  murakkab.  Haqiqatan,  Dehqon,  Suvchi,  C higirtka  uchun 
b irin c h i  algoritm larim izni  eslang.  U larning  to ‘g‘rilig in i  tekshirish
134

---

juda oson edi.  Biz Ijrochin ing har b ir ko ‘rsatmadan keyingi hola tin i 
kuzatib  turar  va  barcha  ko ‘rsatmalar  bajarilgandan  keyin  uning 
ho la ti  masala  shartini  qanoatlantirishiga ishonch  hosil  qUar edik.
Takrorlash tuzUmasini k iritHishi tekshirishni unchalik murakkab- 
lashtirm adi.  Ijrochin ing harakati avvalgidek uning holatiga bog‘liq  
emasdi. Yagona qo‘ shimcha q iy in c h ilik  shundan iborat ediki, juda 
qisqa  yo zu vli  alg o ritm   b a ja rilis h i  natijasida  Ijro c h i  ju da  ko ‘p 
am allarni bajarishi  kerak bo‘lardi.
Shart k iritilishi algoritm ning to ‘g‘rilig in i tekshirishda boshqacha 
aks  etadi.  E ndi  Ijro ch in in g   bajarishi  kerak  bo‘lgan  ko ‘rsatmalar 
ketm a-ketligi  Ijro ch in in g   holatiga  bog‘liq   b o ‘ld i  —  ish  boshida 
K a m a ytiru vch i  ekranida  qanday  son  aks  etib  tu ra rd i,  R obot 
maydonida devorlar qanday joylashgan,  Robot m aydonining  qaysi 
kataklari  b o ‘yalgan.  A lg o ritm n i  oddiygina  b a ja rilish i  va  to ‘g‘r i 
n a tija n i  o lin is h i  algoritm   to ‘g‘r i  ekanligiga  ish ontira  olm aydi. 
A lg o ritm  biz tekshira olgan yoki tekshirishni xohlgan hollardagina 
emas,  balki  ix tiy o riy   holda  ham  to ‘g‘r i  ishlashiga  ishonch  hosil 
qilishim iz kerak. Albatta,  ishonch hosil qilishning eng yaxshi usuli 
—  bu  algoritm   ishining  to ‘g‘rilig in i  isbotlashdir.
R ekursiyani  qo‘llash  yana  tekshirish  q iy in c h lig in i  chuqur- 
lashtiradi.  Haqiqatan,  biz  endi  qaysi  ko ‘rsatma  bajarilayotganini 
kuzatibgina  qolmasdan,  bu  ko‘rsatma  qayerdan  paydo  bo‘lganini 
ham bilishim iz kerak. A ytaylik,  7.1-masala yechim idagi 
simmetriya 
rekursiyasi  is h in i  tekshirayotib,  navbatdagi 
chapga 
ko ‘rsatmasi 
rekursiv  protsedurani  uchinchi  yoki  beshinchi  chaqirishda  paydo 
bo‘lgani va hokazoni yodda saqlashimiz kerak.  Yana agar rekursiv 
protseduralar  algoritm da  ko ‘p  bo ‘lib ,  b ir-b irin i  chaqirsa-chi?
Tekshirish qiyinligi — bu rekursiyalardan foydalanishdan tiyilish n i 
sabablaridan  faqat  birrasidir.  Boshqa  sabablar  ham  bor:  rekursiyali 
dasturlar  rekursiyasiz  dasturlarga  nisbatan  kompyuterda  bajarayot- 
ganda  sekin  ishlaydi  va  xotiradan  ko‘p  jo y   talab  qiladi;  rekursiyali 
dasturlarni  rekursiyasiz  dasturlarga  almashtirayotganda  masalaga 
boshqa  tomondan  qarashga  yordam  beruvchi  ajoyib  fikrla r  paydo 
bo‘lishi mumkin. Shu sababli, masalaning rekursiv yechim ini topgach, 
yana o‘ylab ko‘ring:  rekursiyasiz ishlash m um kin emasmikan?