Urganch davlat universiteti axborot texnologiyalari kafedrasi

 

function C(m,n:

integer

):

longint

; 

begin 

  if (m<=

1

) 

or (n=

0

) 

or (n=m) then C:=

1 

  

else C:=C(m-

1

,n-

1

)+C(m-

1

,n) 

end;

 

 

Argument  qitmatlari  m>1, 0>m>n  bo‘lgan  har  bir chaqiruv  yopishgan  ikkita  chaqiruvni 

keltirib  chiqaradi.  Natijada  har  xil  kattaliklar  takroran  hisoblanadilar.  Masalan,  (5,2) 

argumentlarga  ega  chaqiruvning  bajarilishi  (3,1)  argumentlarga  ega  chaqiruvni  ikki  marta 

bajarilishiga  olib  keladi,  (2,1),  (1,0)  va  (1,1)  argumentlarga  ega  chaqiruvlar  esa  uch  marta 

bajariladi,  yopishgan  chaqiruvlarning  umumiy  soni  1  taga  yetadi.  M qancha  katta  va  m/2  ga  n 

qancha  yaqin  bo‘lsa  yopishgan  chaqiruv  shunch  ko‘p  bo‘ladi.  N  miqdorining  argumentlarga 

bog‘liqligini  aniq  aniqlanmasdan  faqatgina  n=m  div  2  yoki  n=m  div  2+1  da  u  2

m/2 

dan  katta 

ekanligi  ayta  olamiz  (m=60  da  bu  2

30

  yoki  taxminan  10

9

).  Agar  bir  sekund  ichida  10

6

 

chaqiruvlarni  bajarish  mumkin  deb  taxmin  qilsak,  u  holda  C

30

60

  ni  hisoblash  uchun  1000 

sekunddan  yarim  chorak  soatdan  ko‘proq  vaqt  talab  etiladi,  biroq  C

n

m

=C

n-1

m-1

*m/n  ni  aniqlash 

asosida  rekursiv  funksiyani  yozish  kichik  emas  m  argumentli  uni  chaqirish  m/2  dan  ko‘p 

bo‘lmagan  yopishgan  chaqiruvlarni  keltirib chiqaradi.  Yuqorida  C  funksiya  faqat rekursiyaning 

o‘ylanishsiz  ishlatilish  misol  sifatida  keltirilgan.  Yopishgan  miqdorining  ko‘chkisimon  sababi 

ushbu  masala  uchun  majbur  bo‘lgan  funksiya  tanasidan  ikki  chaqiruv  hisoblanadi.  Binomial 

koeffisienti  va  boshqa  rekurent  ketma  ketliklarni  elemetlarini  rekursiya  emas  uning  yordamida 

hisoblash  afzalroq.  Dasturostining  har  chaqiruvini  bajarish  argumentlarini  qo‘yilishida 

qo‘shimch  harakatlarni  talab  etadi,  shuning  uchu  odatda  siklik  variant  uncha  mos  keluvchi 

variantga nisbatan tezroq bajariladi. 

 

 Rekursiya  chuqurligi  ajratilgan  aftomatik  xotira  o‘lchamiga  yopishgan  chaqiruvlarning 

umumiy miqdoriga esa -bajarish davomiyligi ta’sir qiladi.  Rekursiya chuqurligi katta bo‘lganda 

aftomatik xotira yo‘nalishiga va dasturni avtomatik tugallanishini xabari mavjud bo‘ladi. 

 

Rekursiya  o‘ziga  cheksiz  miqdorda  hisoblashlarni  yopishgan  sikllar  “yashirgandan” 

yetarlicha osonroq “yashiradi”. Rekursiv dasturostilarni ishlata turib rekursiyani mumkin bo‘lgan 

chuqurligin va chiqaruvchilarni umumiy miqdorini boholashni o‘rganing. 

 

Rekursiv  ta’rif  bo‘yicha  bevosita  rekursiv  dasturostining  yozishga  shoshilmang  –  oddiy 

va  qisqa  dasturosti  juda  uzoq  vaqt  bajarilishi  mimkin.  Rekurent  ketma-ketliklar  elementlar, 

ayniqsa agar munosabat tartibi 1 dan katta bo‘lsa rekursiyani qo‘llamang . 

 

Shunday  bo‘lsada  rekursiyani  o‘rnida  qo‘llanilishi  oson  va  tabiiy  dasturlarni  yaratishga 

yengil va tez imkon beradi .