|
19-Labaratoriya ishi.
Mavzu: Vazn oralig’ini rejalashtirish: rekursiv jarayonlar
Rekursiya va stack
Vazifalarga qaytaylik va ularni batafsilroq ko'rib chiqamiz.
Bizning birinchi mavzuimiz rekursiya bo'ladi.
Agar siz dasturlash uchun yangi emas bo'lsangiz, siz allaqachon rekursiya bilan tanish bo'lishingiz mumkin va siz ushbu bobni o'tkazib yuborishingiz mumkin.
Rekursiya - bu vazifani tabiiy ravishda bir nechta o'xshash, ammo sodda vazifalarga bo'lish mumkin bo'lgan holatlarda foydali bo'lgan dasturlash usuli. Yoki biron bir vazifani sodda harakatlarga soddalashtirish mumkin bo'lsa, xuddi shu vazifaning oddiy versiyasi. Yoki, yaqinda bilib olamizki, ma'lum bir tuzilmalar bilan ishlash uchun.
Vazifani bajarish jarayonida subkastrlarni bajarish uchun boshqa funktsiyalarni funktsiyaning tanasida chaqirish mumkin. Sub-qo'ng'iroqning alohida holati bu funktsiya o'zini o'zi chaqirganda. Bu rekursiya deb ataladi.
Fikrlashning ikki yo'li
Birinchi misol sifatida, x n kuchini n ga ko'taradigan pow (x, n) funktsiyasini yozamiz. Boshqacha aytganda, x ni n marta ko'paytiradi.
pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16
:
function pow(x, n) {
let result = 1;
// умножаем result на x n раз в цикле
for (let i = 0; i < n; i++) {
result *= x;
}
return result;
}
alert( pow(2, 3) ); // 8
:
function pow(x, n) {
if (n == 1) {
return x;
} else {
return x * pow(x, n - 1);
}
}
alert( pow(2, 3) ); // 8
Ichki qo'ng'iroqlarning umumiy soni (birinchi qatorni ham qo'shgan holda) rekursiya chuqurligi deb ataladi. Bizning holatda, u aniq n bo'ladi.
Maksimal rekursiya chuqurligi JavaScript mexanizmi tomonidan cheklangan. Siz 10000 kirgan qo'ng'iroqlarni aniq hisoblashingiz mumkin, ba'zi tarjimonlar ko'proq imkoniyat berishadi, ammo ularning ko'plari uchun 100 mingta qo'ng'iroqlar imkoniyatlardan tashqarida. Avtomatik optimallashtirish mavjud bo'lib, ular qo'ng'iroqlar to'plamini ("quyruq rekursionini optimallashtirish") toshib ketishini oldini olishga yordam beradi, ammo ular hali ham hamma joyda qo'llab-quvvatlanmaydi va faqat oddiy holatlar uchun ishlaydi.
Bu recursiondan foydalanishni cheklaydi, ammo u hali ham keng tarqalgan: ko'p sonli muammolarni hal qilish uchun rekursiv hal qilish usuli sodda sodda kodni beradi.
Bajarish konteksti, qoziq
Endi biz rekursiv qo'ng'iroqlar qanday ishlashini bilib olamiz. Buning uchun funktsiyalarning "kaputi ostiga" qarang.
Ishga tushirilgan funktsiyaning bajarilish jarayoni to'g'risidagi ma'lumotlar uning bajarilish kontekstida saqlanadi.
Bajarish konteksti funktsiyani chaqirish haqida ma'lumotni o'z ichiga olgan maxsus ichki ma'lumotlarning tuzilishi. U tarjimon joylashgan kodning o'ziga xos joyini, funktsiyaning mahalliy parametrlarini, uning qiymatini (biz ushbu misolda ishlatmaymiz) va boshqa qo'shimcha ma'lumotlarni o'z ichiga oladi.
Bitta funktsiya chaqiruvi aniq bitta bitta bajariladigan kontekstga bog'liq.
Agar funktsiya o'rnatilgan qo'ng'iroqni amalga oshirsa, quyidagilar sodir bo'ladi:
Joriy funktsiyaning bajarilishi pauza qilingan.
U bilan bog'liq bo'lgan ijro etilish konteksti maxsus ma'lumotlar strukturasida - ijro kontekstlarining to'plamida saqlanadi.
Ichki qo'ng'iroqlar amalga oshiriladi, ularning har biri uchun ijro etilishning boshqa konteksti yaratiladi.
Ular tugallangandan so'ng eski kontekst stekandan olinadi va tashqi funktsiyaning bajarilishi to'xtatilgan joydan boshlanadi.
Misol sifatida toz (2, 3) funktsiyasidan foydalanib, kontekstlarni batafsil ko'rib chiqamiz.
pow (2, 3)
Pow (2, 3) chaqirig'ining boshida, ijro konteksti o'zgaruvchilarni saqlaydi: x = 2, n = 3, ijro funktsiyaning birinchi qatorida joylashgan.
Siz sxematik tarzda quyidagicha tasvirlashingiz mumkin:
Kontekst: {x: 2, n: 3, 1-qator} pow (2, 3)
Bu faqat funktsiyaning boshlanishi. N == 1 sharti noto'g'ri, shuning uchun ijro ikkinchi tarmoqqa o'tadi, agar::
function pow(x, n) {
if (n == 1) {
return x;
} else {
return x * pow(x, n - 1);
}
}
alert( pow(2, 3) );
Boshqacha aytganda, kompaniyada bo'limlar mavjud.
Bo'lim bir ator xodimlardan iborat bo'lishi mumkin. Masalan, savdo bo'limida 2 nafar xodim ishlaydi: Jon va Elis.
Yoki bo'limni bo'linmalarga bo'lish mumkin, masalan, rivojlanish bo'limi bo'limlardan iborat: saytlar va ichki. Har bir bo'lim o'z xodimlariga ega.
Bo'linmaning o'sishi bilan u birliklarga (yoki jamoalarga) bo'linishi ham mumkin.
Masalan, kelgusida saytlar bo'linmasini saytA va saytB buyruqlariga bo'lish mumkin. Va ehtimol ular hali ham ulashilishi mumkin. Bu rasmda emas, shunchaki buni yodda tutishingiz kerak.
Endi barcha ish haqi miqdorini olish uchun bizga funktsiya kerak deylik. Buni qanday qilishimiz mumkin?
Iterativ yondashuv oddiy emas, chunki struktura ancha murakkab. Birinchi g'oya - bu 1-darajali joylashish bo'limlari ustidan kompaniya ob'ekti ustiga pastadir uchun tsikl qilish. Ammo keyin biz ikkinchi darajali bo'limlarning, masalan saytlarning ishchilari ustidan ishora qilish uchun ko'proq ichki teshiklarni talab qilamiz ... Va kelajakda paydo bo'lishi mumkin bo'lgan uchinchi darajali bo'limlar uchun yana bir tsikl kerakmi? Agar bitta ob'ektni kesib o'tish uchun kodga 3-4 teshik joylashtirsak, u juda xunuk bo'ladi.
Keling, rekursiyani sinab ko'raylik.
Ko'rib turganimizdek, bizning vazifamiz ish haqi miqdorini hisoblash uchun bo'limni olganda, ikkita mumkin bo'lgan holatlar mavjud.
Yoki u "oddiy" bo'lim bilan massivmi - shunda biz oddiy ish tsiklida ish haqini umumlashtirishimiz mumkin.
Yoki u N bo'linmalari bilan ob'ektmi - keyin biz har bir bo'linma uchun yig'indini olish uchun N rekursiv chaqiruvlarni amalga oshiramiz va natijalarni birlashtiramiz.
Masala (1), biz qatorga ega bo'lganimizda, rekursion asos, arzimas holat
Case (2), ob'ektni olgandan so'ng, rekursiya bosqichidir. Qiyin vazifa pastki bo'limlarga bo'linadi. Ular, o'z navbatida, yana bo'linmalarga bo'linishi mumkin, ammo ertami-kechmi bu bo'linish tugaydi va echim bu ish uchun kamayadi (1)
Foydalangan adabiyotlar:
M.Aripov, A.Haydarov,Informatika asoslari Toshkent 2002-yil.
A.A.Abduqodirov , A.G’Hayitov.Axborot texnalogiyalari, Toshkent <> 2003-yil.
Ziyonet.uz , yandex.uz ,google.
Do'stlaringiz bilan baham: | 
