Urganch davlat universiteti axborot texnologiyalari kafedrasi

3.1.3 Rekursiya chaqirilishi va rekursiv chaqiruvlarning umumiy miqddori. 

Rekursiv dasturostilari bilan rekursiv dastur ostining chaqiruvchi tufayli  kelib chiquvchi 

ikki zarur tushunchaga-rekursiya chuqurligi va chaqiruvlarning umumiy miqdori bog‘langan. 

Dasturosti chaqiruvchining rekursiya chuqurligi-ushbu chaqiruv bajarilganida tugallanmagan 

rekursiv chaqiruvlarning maksimal miqdori. 

 

Masalan  3  argumentli  n!  ni  hisoblash  funksiyasining  chaqiruvi  faqat  2  argumentli 

chaqiruv tugallangandan keyin. uniki esa 1 argumentli chaqiruv tugallangandan keyin to‘xtaydi. 

Ayniqsa  n!  argumentli  chaqiruv  yana  n  ta  chaqiruv  keltirib  chiqaradi.  Shuning  uchun 

tugallanmagan chaqiruvlarning soni maksimal soni n! ni  hisoblaganda yani rekursiya chuqurligi 

n+1 gacha yetadi. 

Eng  chuqur  chaqiruvning  o‘zi  bajarilganda  m  rekursiya  chuqurligini  chaqiruv 

bajarilayotganda  bir  vaqtning  o‘zida  lokal  xotiraning  m  nusxalari  “mavjud  bo‘ladi”.  Har  bir 

nusxalar  ma’lum  bir  o‘lchamga  ega  va  agar  chuqurlik  o‘ta  katta  bo‘lganida  u  holda  dastur 

bajarilish jarayoniga taqdim etilgan avtomatik xotira etmasligi mumkin. 

 

Eslatma:  avtomatik  xotira  o‘lchamini  tuzib  sozlashda  yoki  {SM…}  kompilyatorga 

direktivalar  yordamida  o‘rnatish  mumkin.  Diqqat  qarating  aynan  ushbu  direktuvaning  Turbo 

Paskal , Free Paskal Delphidagi sintaksisi turlicha. 

 

Turbo  muhitida  rekursiv  dastur  ostining  qadamma-qadam  bajarilishini  kuzatib  nafaqat 

dastlabki matindagi pozitsiyasiga, balki dastur stekining ichidagilarga ham, Call Stack (“ctrl+f3” 

klavishlar)  kamandalarini  ishlatib,  diqqat  qarating.  Ushbu  kamanda  bo‘yicha  dasturning  stekda 

real joylashgan barcha narsalarni ham muhim ko‘rsatavermaydi. 

 

Rekursiv  dastur  ostilar  uchun  StepOver(  klavish)  komandasi  bajarib  turbo  muhit 

rekursiv  dasturosti  chaqiruvchi  tugallangandan  keyin  dastur  holatini  namayon  qiladi  (shunday 

bo‘lishi  kerak).  Biroq  bosilganida  bajarilishi  boshlangan  chaqiruv  bo‘lmasdan  boshqasi 

unga nisbatan yopishtirilgan yani kutilgani ems boshqasi tasvirlangan bo‘lishi mumkin. 

 

Rekursiv dastur ostining ushbu chaqiruv keltirib chiqargan yopishtirilgan chaqiruvlarning 

umumiy  miqdori  –  ushbu  chaqiruv  boshlanishi  va  tugallanishi  orasidagi  bajarilgan 

---

chaqiruvlar miqdoridir. 

 

Misol.  Binominal  koefisientlari  rekursiv  aniqlanadilar:  agar  0≤m≤1  yoki  n=0  yoki  n=m 

bo‘lsa  C

n

n

=1  aks  holda  C

m

n

=C

m-1

n-1

+C

m-1

n

  binominal  koefisient  C

m

n

  ning  m  va  n  bo‘yicha 

hisblashning rekursiv funksiyalarini qaraymiz, bu yerda 0≤n≤m.