Rekursiya (umuman) – bu ob’ektni mazkur ob’ektga murojat qilish orqali aniqlashdir.
Izoh
Rekursiv algoritm – bu algoritmi aniqlashda o’ziga bevosita yoki bilvosita murojat qilishdir.
Eslatma: Algoritm va dasturlarni tuzishda rekursiyadan foydalanish vaqtni tejaydi, hajmi kichi bo’ladi, lekin interaksion usulga isbatan dastur sekinroq ishlaydi hamda ko’proq hotira talab qiladi.
Def.1.
Agar ma’lumotlar tuzilmasi elementlari ham mazkur tuzilmaga o’xshash tuzilma bo’lsa , u holda bunday tuzilmaga rekursiv ma’lumotlar tuzilmasi deyiladi.
Darat o’zining quyidagi belgilari bilan tasniflanadi:
Daraxtda shunday bitta element borki, unga boshqa elementlardan murojat yo’q. Mazkur elementga daraxt ildizi deyiladi;
Daraxtda ixtiyoriy elementga chekli sondagi ko’rsatgichlar yordamida murojaat qilish mmkin;
Daraxtning har bir elementi faqatgina o’zidan oldingi kelgan bitta element bilan bog’langan. Daraxtning har bir tuguni orqali yoki terminal (barg bo’lishi mumkin.
Def.2.
Daraxt bosqichlari soniga daraxt balandligi deyiladi.
Def.3.
Tugunlardan chiqayotgan shohlar soni tugundan chiqish darajasi deyiladi.
Mantiqiy tasvirlashda daraxtlar bog’langan ro’yhatlar ko’rinishda ifodalanadi. Bunda ro’yhat elementi tugun qiymati va chiqish darajasini o’z ichiga oluvchi information maydonga hamda chiqish darajasiga teng bo’lgan ko’rsatkichlar maydoniga ega bo’ladi.
Daraxt grafik va chiziqsiz ro’yhat shaklidagi tasvirlanishi.