2-Amaliy mashg’ulot. Mavzu- rekursiya yordamida algoritmlarni qurish. Rekursiv funksiyalar

---

2-Amaliy mashg’ulot.  

Mavzu- Rekursiya yordamida algoritmlarni qurish. 

Rekursiv funksiyalar. Funksiya tanasida o‘zini o‘zi chaqirsa rekursiya deyiladi. 

Rekursiya ikki xil bo‘ladi: 

Oddiy – agar funksiya o‘z tanasida o‘zini chaqirsa; 

Vositali – agar birinchi funksiya ikkinchi funksiyani chaqirsa, ikkinchisi esa o‘z 

navbatida birinchi funksiyani chaqirsa. 

Odatda rekursiya matematikada keng qo‘llaniladi. Chunki aksariyat matematik 

formulalar rekursiv aniqlanadi. 

 Rekursiv 

funksiya 

deb, 

o`ziga 

o`zi 

murojaat 

qiluvchi 

funksiyaga  aytiladi.  Rekursiya  –  shunday  jarayonki,  bunda  jarayonni  borishi  o’ziga 

murojaat qilish bilan bog’liq bo’ladi.. 

Rekursiv  ma’lumotlar  tuzilmasiga  misol  qilib  shunday  tuzilmalarni  olish 

mumkinki,  ushbu  tuzilmalarning  elementlarining  o’zi  xam  xuddi  shunday  tuzilma 

bo’ladi (qarang, chizma). 

 

Daraxtlar  

  Daraxt 

– 

bu 

chiziqsiz 

bog’langan 

ma’lumotlar 

tuzilmasidir 

(qarang, chizma).  

 

Daraxt o’zining quyidagi belgilari bilan tasniflanadi: 

 -  daraxtda  shunday  bitta  element  borki,  unga  boshqa  elementlardan  murojaat 

yo’q. Mazkur elementga daraxt ildizi deyiladi; 

 -  daraxtda  ixtiyoriy  elementga  chekli  sondagi  ko’rsatkichlar  yordamida 

murojaat qilish mumkin; 

 -  daraxtning  har  bir  elementi  faqatgina  o’zidan  oldingi  kelgan  bitta  element 

bilan  bog’langan.  Daraxtning  har  bir  tuguni  oraliq  yoki  terminal  (barg)  bo’lishi 

mumkin. Yuqoridagi chizmada M1, M2 - oraliq, A, B, C, D, E - barglardir. Terminal 

tugunning o’ziga xos tasnifi uning shoxlari yo’qligidir. 

---

Balandlik  –  bu  daraxt  bosqichi  soni.  Yuqoridagi  chizmadagi  daraxt  balandligi 

ikkiga teng. 

Daraxt tugunlaridan chiqayotgan shohlar soni tugundan chiqish darajasi deyiladi 

(Keltirilgan  chizmada  M1  uchun  chiqish  darajasi  2,  M2  uchun  esa  3  ga  teng). 

Daraxtlar chiqish darajasi bo’yicha sinflarga ajratiladi: 

1) agar maksimal chiqish darajasi m bo’lsa, u holda bunday daraxt m-chi tartibli 

daraxt deyiladi; 

2)  agar  chiqish  darajasi  0  yoki  m  bo’lsa,  u  holda  to’liq  m-chi  tartibli  daraxt 

bo’ladi;        

3) agar maksimal chiqish darajasi 2 bo’lsa, u holda bunday daraxt binar daraxt 

deyiladi; 

4) agar chiqish darajasi 0 yoki 2 bo’lsa, u holda to’liq binar daraxt deyiladi.  

ugunlar  orasidagi  bog’liqlikni  tavsiflash  uchun  yana  quyidagicha  termindan 

foydalaniladi:  M1  –  A  va  V  elementlar  uchun  “ota”  .  A  va  V  –  esa  M1  tugun 

“o’g’illari”.