Urganch davlat universiteti axborot texnologiyalari kafedrasi

3 bob. Rekursiya. 

3.1. Asosiy tushunchalar 

3.1.1. Rekursiv ta’riflar 

Rekursiv ta’rif ushbu to‘plamning boshqa elementlari  yordamida qandaydir to‘plamning 

boshqa  elementlari  yordamida  qandaydir  to‘plamning  elementlarini  beradi.  Shunday 

ta’riflarni ishlatish rekursiya deyiladi. 

 

Masalan faktorial funksiyasining qiymatlari n!=n*(n-1)! Ifoda bilan beriladi, bunda 0!=1 . unda 

1!=1*0!=1, 2!=2*1!=2; 3!=3*2!=6 va shu kabilar. Birinchidan boshqa barcha qiymatlar rekursiv 

aniqlanadi.  Rekursiv  ta’rifda  “sehlanagan  aylana”  bo‘lishi  mumkin  emas,  bunday  obyektni 

aniqlashda  uning  o‘zi  yoki  uning  yordamida  berilgan  boshqa  obyektlar  ishlatiladi.  Masalan, 

“faktorial”  funksiyasining  ta’rifini  n>0,  0!=1!  da  quyidagicha  o‘zgartiramiz:  n!=n*(n-1)! 

“sehrlangan aylana”  1 dan  funksiya  qiymati  uning  0 dan  qiymati  orqali  u  esa,  o‘z  navbatida, 1 

dan  qiymati  ifodalanadi.  Shuning  uchun  ushbu  ta’rif  bo‘yicha  1!  nimaga  teng  bo‘lishini  bilish 

imkoni  yo‘q.  Quyidagi  shartlarni  ta’minlab  o‘xshah  “sehrlangagn  aylana”lardan  voz  kechish 

mumkin: 

  Aniqlanuvchi obyektlar to‘plami qisman tartiblangan hisoblanadi; 

  Ushbu  tartib  bo‘yicha  kamayayotgan  elementlarning  har  bir  ketma-ketligi  qandaydir 

minimal element bilan tugallanadi. 

  Minimal elementlar rekursiv ekanligi aniqlanadi; 

  Nominimal  elementlar  ulardan  ushbu  tartiblanish  bo‘yicha  kichik  bo‘lgan  elementlar 

yordamida aniqlanadi. 

Kimga  qisman  tartiblangan  to‘plam  va  minimal  elementlar  terminlari  tanish  bo‘lmasa  , 

qisqacha  norasmiy  tushuntirish  beramiz.  Qandaydir  to‘plam  elementlarini  (hammasi  shartmas) 

taqqoslash,  ya’ni 

b

a 

  (“a  b  dan  katta  emas“)  ekanligini  aniqlashtirish  mumkin  deb  taxmin 

qilamiz.  Agar  bunda  a  va  b  turlicha  bo‘lsa,  u  holda  “a  b  dan  kichik“  deydilar.  Elementlar 

taqqoslanmaganligi  ham  mumkin.  Qachonki 

a

b

ham

b

a





ham  bajarilmasa.  Masalan  agar 

“katta emas“ sifatida natural sonlar orasida “bo‘lish munosabatini olsak, u holda bir boshqa har 

qanday  natural  sondan  kichik,  2  va  3  esa  o‘zlari  orasida  tengsizdir.  To‘plam  elementlari 

orasidagi munosabat agar quyidagi holatlarga ega bo‘lsa qisman tartib munosabati deyiladi. 

 

1. Har bir a uchun 

a

a  ekanligi to‘g‘ri (elementlar o‘zlaridan katta emas ) . 

2. Turlicha a va b lar mavjud emaski, ular uchun bir vaqtda 

a

b

va

b

a





 

3.  Istalgan  a  b  c  elementlar  uchun  agar 

c

b

va

b

a





  to‘g‘ri bo‘lsa  u  holda 

c

a    ham 

to‘g‘ri. To‘plamlar turlicha bunday elementlar bo‘lmasligi ham mumkin. Faqat a va b dan kichik, 

b  c  dan  kichik  va  a  c  dan  kichik  bo‘lmasa  yetarli.  Birinchi  xossa:  Refleksivlik,  ikkinchi  –

aktisimimentriklik,  uchinchi  –  trakzitivli  deyiladi.  Orasidagi  munosabatlari  qisman  tartibli 

bo‘lgan  elementlar  to‘plami  qisman  tartiblangan  deyiladi.  Agarda  to‘plamda  a  kichik  element 

bo‘lmasa uning elementi minimal deyiladi. Misollarni ko‘ramiz: Natural sonlar to‘plami “bo‘lish 

ga  nisbatan  qisman  tartiblangan  nuqta  unda  bitta  minimal  element  bor  1  soni,  biroq  agar  u 

chiqarib  tashlansa  u  holda  minimal  elementlar  bo‘lib  barcha  oddiy  sonlar  bo‘ladi.  n! 

funksiyalarning  qiymatlarining  argument  qiyamatlarining  o‘sish  tartibidir  va  0!  Minimal 

hisoblanadi.  Takidlash  kerakki,  0!  Rekursiyasiz  aniqlangan  qolgan  qiymatlari  esa  kichik 

argumanetlar,qiymatlar yordamida topiladi.