Ajrat va hukmronlik qil

LABORATORIYA ISHI - 25
Mavzu: “Ajrat va hukmronlik qil” prinsipi bo’yicha ishlaydigan algoritmlarni loyihalash.
Ishdan maqsad. “Ajrat va hukmronlik qil” prinsipi bo’yicha ishlaydigan algoritmlarni loyihalashni o’rganish.
Qo’yilgan masala. “Ajrat va hukmronlik qil” prinsipi bo’yicha ishlaydigan algoritmlarni loyihalash.
Ish tartibi:

• 
  Tajriba ishi nazariy ma’lumotlarini o‘rganish;
  
• 
  Berilgan topshiriqning algoritmini ishlab chiqish;
  
• 
  C++ dasturlash muhitida dasturni yaratish;
  
• 
  Natijalarni tekshirish;
  
• 
  Hisobotni tayyorlash va topshirish.
  

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.

Rekursiyadan chiqish
Rekursiv protseduralarni har qanday Ijrochi uchun yozish mumkin. Masalan, Robotni kvadrat bo‘y!ab yurishi uchun rekursiv protsedura yozaylik.
7.4-masala
Tomoni 5 ga teng kvadratni chizish rekursiv protsedurasini
yozing. Javob.
PROT rekursiv kvadrat
BOSHLANISH
oldinga oldinga
oldinga oldinga
oldinga o‘ngga
rekursiv kvadrat TAMOM
Bu protsedura qanday ishlashini ko‘rib chiqamiz. Demak, rekursiv kvadrat protsedurasi chaqirilganda oldinga oidinga
oldinga oldinga oldinga
0‘ngga ko‘rsatmalari bajariladi. Bunda Robot kvadratning tomoni bo‘ylab yurib 90 gradusga buriladi. Keyin yana rekursiv kvadrat protsedurasi chaqiriladi. Robot kvadratning boshqa tomoni
bo'ylab yurib o'ngga buriladi. Keyin yana rekursiv kvadrat protsedurasi chaqiriladi. Yana ikki tomon o'tilgach kvadrat
bo‘ylab yurish yakunlanadi. Lekin nimadir bo‘ldi? Robot to'xta- masdan yana shu kvadrat bo'ylab yurishni davom ettirmoqda. Bu esa cheksiz davom etadi — algoritm siklga tushib qoldi. Vaziyat yoqimsiz. Biz doimo siklga tushib qolmaslikka harakat qilar edik. Bu holda undan qutulishning chorasi bormikan? Taas- sufki, yo‘q. Haqiqatan, rekursiv protseduraning chaqirilishi cheksiz davom etmasligi uchun protseduraga chaqirilish yuzaga kelmaydigan shart kiritish kerak. Lekin bu Robotda bunday shart yo‘q. Robotning algoritmi uning holatidan qa’tiy nazar,
bir xilda bajarilaveradi. Shu kabi, Dehqon, Suvchi, Chigirtka, Oshiruvchi, Zohid kabi Ijrochilarda shart yo‘q. Bu Ijrochiiar uchun rekursiv protseduraning qo‘lianishi yoki siklga tushib qolinadi yoki keyingi ko'rsatmani bajarish mumkin bo'lmay qolib, INKOR yuzaga keladi. Shuning uchun Sharti yo'q Ijrochilar uchun rekursiv protseduralarni qo’llamang!
Bu qo’llanmada ko‘rib chiqilgan Ijrochilardan faqat Kamaytiruvchi va Robotda shart bor. Demak, faqat shu ikki Ijrochi uchun rekursiv protseduralami yozish ma'noga ega. Bizning mulohazalarimizdan shunday xulosaga kelish mumkin; Rekursiv protseduralarni yozganda rekursiv chaqirish yuzaga kelmaydigan shart ko‘rsatilishi kerak.
Bu juda kerakli xulosa! Shuning uchun ham awalgi bo‘limda algoritm namunalarini keltirganimizda, rekursiv protsedu- ralarning shunday shartlarini va zaruriy amallarining tavsifini yozishdan boshlaganmiz.