Algoritm tahlilining asoslari. Algoritmlar va uning xususiyatlari. Rekursiv algoritmlar, Rekurrent munosabatlari. Iterativ algoritmlar. Asosiy algoritmlar. Qidiruv va saralash algoritmlari

Download 2,45 Mb.
bet	4/6
Sana	29.05.2024
Hajmi	2,45 Mb.
	#256522

1 2 3 4 5 6

Bog'liq
Algoritm tahlili asoslariga kirish

Nima uchun rekursiya kerak

Rekursiv algoritmlar

Rekursiya - ob'ektlarni (tushunchalarni) aniqlash usuli bo'lib, unda ob'ektning ta'rifi ob'ektning o'zi kontseptsiyasidan kelib chiqqan holda quriladi.
Algoritmning tavsifi to'g'ridan-to'g'ri yoki bilvosita o'ziga tegishli bo'lsa, u rekursiv deb ataladi.
Rekursiv funktsiya o'zini chaqiradigan funktsiyadir.
Masalan, faktorialni hisoblash
А! = А  (А – 1)!
Rekursiya - bu asl masalani bir xil turdagi bir yoki bir nechta sodda masalalarga qisqartirish imkonini beruvchi texnikadir.
Rekursiya hodisalarning naqshini ko'rsatadi.
Rekursiyani aniqlash uchun siz quyidagilarni belgilashingiz kerak:
- takrorlanuvchi formula
- rekursiyani to'xtatish sharti.
Har qanday rekursiyani sikl yordamida dasturlash mumkin.
Rekursiya siklni almashtirishga imkon beradi va ba'zi murakkab masalalarda yechimni tushunarli qiladi, garchi ko'pincha unchalik samarali emas.
Masala: korobkalar ichma-ich ixtiyoriy joylashtirilgan, qaysidir korobka ichida kalit bor. Siz kalitni topish dasturini tuzing
Rekursiyaga qoyish uchun ushbu ikki shart yozib olamiz: 1. Ishlash sharti: korobka ichida korobka chiqsa, uni ochib ko'r 2. To'xtash sharti: korobka ichidan kalit chiqsa to'xta
Rekursiv funksiyaning to'xtash chegarasi bo'lmasa esa, amallar cheksiz bajarilaveradi, oqibatda crash beradi, yoki dastur osilib qoladi. Xo'sh nega?
Funksiya ishga tushganda keyingi chaqirilayotgan funksiya STACKka qo'shib borilaveradi. Rekursiv funksiya ishlaganda o'zi o'zi chaqirishini ayttim, aynan chaqiruvchi funksiya esa chaqirilgan funksiyani natijasini kutib turadi, u esa o'zi chaqirgan funksiya natijasiga bog'liq bo'ladi .... va hokazo toki to'xtash nuqtasidagi funksiyaga borgunicha. Oxirgi nuqtadagi funksiya ishlaganda esa, stackdan chiqib ketib undan oldingisi bajarilib, undan oldingisiga javob yetib boradi ... va hokazo eng birinchi chaqirilgan funksiya eng oxirida yopiladi.

Nima uchun rekursiya kerak?

Har qanday rekursiv ishlangan masalani iterativ usulda ishlash mumkin va buning aksi ham to’g’ri. Buning ustiga rekursiv yechim har doim xotiradan qo’shimcha joy talab qiladi.
Shunday ekan, nima uchun unda rekursiya kerak? Albatta, buning yetarlicha sabablari bor:

Download 2,45 Mb.

1 2 3 4 5 6

Download 2,45 Mb.