Rekursiya va stek

Keling, funktsiyalarga qaytamiz va ularni yanada chuqurroq o’rganamiz.

Bizning birinchi mavzuimiz rekursiya bo’ladi.

Agar siz dasturlash bilan yangi tanish bo’lmasangiz, ehtimol u sizga tanish va siz ushbu bobni o’tkazib yuborishingiz mumkin.

Rekursiya – bu vazifa tabiiy ravishda bir nechta o’xshash, ammo oddiy vazifalarga bo’linishi mumkin bo’lgan hollarda foydali bo’lgan dasturiy ta’minot usuli. Yoki vazifa oddiy ishlarga, shuningdek, bir xil vazifaning oddiy versiyasiga soddalashtirilishi mumkin. Yoki yaqinda ko’rib chiqamiz, muayyan ma’lumotlar tuzilmalari bilan ishlash.

Funktsiya vazifani bajarganda, u boshqa ko’plab funktsiyalarni chaqirishi mumkin. Buning qisman holati shundaki, funktsiya o’zini chaqiradi. Bunga rekursiya deyiladi.

Fikrlashning ikkita usuli

Biron bir oddiy narsadan boshlash uchun – keling, x ni n ning natural darajasiga ko’taradigan pow(x,n) funktsiyasini yozaylik. Boshqacha qilib aytganda, x o’z-o’zini n marta ko’paytiradi.

pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

Uni amalga oshirishning ikki yo’li mavjud.

1. Takroriy fikrlash: for tsikli:

   function pow(x, n) {
     let result = 1;
   
     // natijani ko'chadan x n marta ko'paytirish
     for (let i = 0; i < n; i++) {
       result *= x;
     }
   
     return result;
   }
   
   alert( pow(2, 3) ); // 8

2. Rekursiv fikrlash: vazifani soddalashtiring va o’zini chaqiring:

   function pow(x, n) {
     if (n == 1) {
       return x;
     } else {
       return x * pow(x, n - 1);
     }
   }
   
   alert( pow(2, 3) ); // 8

Iltimos, rekursiv variant qanday fundamental farq qilishiga e’tibor bering.

pow(x,n) chaqirilganda, ijro ikkita shoxga bo’linadi:

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

1. Agar n == 1 bo’lsa, unda hamma narsa ahamiyatsiz. U rekursiyaning bazasi deb nomlanadi, chunki u darhol aniq natijani beradi: pow (x, 1) teng x.
2. Aks holda, biz pow(x, n) ni x * pow (x, n - 1) sifatida ifodalashimiz mumkin. Matematikada xn = x * xn-1 yozish mumkin. Bu rekursiv qadam deyiladi: biz vazifani oddiyroq harakatga aylantiramiz (x ga ko’paytirish) va xuddi shu vazifani oddiyroq chaqiruviga (pow pastroq n bilan). Keyingi qadamlar uni yanada soddalashtiradi va n 1 ga yetguncha.

Shuni ham aytishimiz mumkinki, pow rekursiv ravishda o’zini n == 1 gacha chaqiradi.

Yoki masalan, pow(2, 4) ni hisoblash uchun rekursiv variant quyidagi bosqichlarni bajaradi:

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) = 2 * pow(2, 1)
4. pow(2, 1) = 2

Shunday qilib, rekursiya funktsiya chaqiruvini sodda chaqiruvchiga, so’ngra yanada soddalashtirishga va hokazo natija aniq bo’lguncha kamaytiradi.

function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

Ichki chaqiruvlarning maksimal soni (birinchisini ham qo’shganda) rekursiya chuqurligi deb nomlanadi. Bizning holatda, bu aniq n bo’ladi.

Maksimal rekursiya chuqurligi JavaScript interpretatori bilan cheklangan. 10000 ga yaqin ekanligiga ishonch hosil qilishimiz mumkin, ba’zi interpretatorlar ko’proq narsalarga imkon beradi, ammo 100000 ularning aksariyati uchun cheklangan bo’lishi mumkin. Buni engillashtirishga yordam beradigan avtomatik optimallashtirishlar mavjud (“quyruq chaqiruvlar optimallashtirish”), ammo ular hali hamma joyda qo’llab-quvvatlanmaydi va faqat oddiy holatlarda ishlaydi.

Endi rekursiv chaqiruvlar qanday ishlashini ko’rib chiqamiz. Buning uchun biz funktsiyalarning “qopqog’ ostini” ko’rib chiqamiz.

Funksiyaning ishlashi haqida ma’lumot uning bajarilish kontekstida saqlanadi.

Ijro etish konteksti – bu funktsiyalarning bajarilishi to’g’risidagi ma’lumotlarni o’z ichiga olgan ichki ma’lumotlar tuzilishi: boshqaruv oqimi hozir bo’lgan joyda, hozirgi o’zgaruvchanlar , this qiymati (biz bu yerda ishlatmaymiz) va boshqa bir nechta ichki tafsilotlar.

Bitta funktsiya chaqiruvi u bilan bog’liq bo’lgan bitta ijro kontekstiga ega.

Funktsiya ichki chaqiruvni amalga oshirganda, quyidagilar sodir bo’ladi:

• Joriy funktsiya to’xtatildi.
• U bilan bog’liq bo’lgan ijro konteksti ijro kontekst steki deb nomlangan maxsus ma’lumotlar tuzilmasida eslab qolinadi.
• Ichki chaqiruv amalga oshiriladi.
• U tugagandan so’ng, stekdan eski ijro konteksti olinadi va tashqi funktsiya to’xtagan joyidan tiklanadi.

Keling, pow(2, 3) chaqiruvi paytida nima sodir bo’lishini ko’rib chiqaylik.

pow(2, 3)

pow(2, 3) chaqiruvining boshida bajarilish konteksti o’zgaruvchanlarni saqlaydi: x = 2, n = 3, ijro oqimi funktsiyaning 1 satrida.

Biz uni quyidagicha chizishimiz mumkin:

• Kontekst: { x: 2, n: 3, 1-satrda} pow(2, 3)

Ana shunda funktsiya bajarila boshlaydi. n == 1 sharti noto’g’ri, shuning uchun oqim if ning ikkinchi shoxiga o’tadi:

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) );

O’zgaruvchanlar bir xil, ammo satr o’zgaradi, shuning uchun kontekst hozir:

• Kontekst: { x: 2, n: 3, 5-satrda } pow(2, 3)

x * pow (x, n - 1) ni hisoblash uchun biz yangi pow(2, 2) argumentlari bilan pow subchaqiruvini qilishimiz kerak.

pow(2, 2)

Ichki chaqiruvni amalga oshirish uchun JavaScript ijro kontekst stekidagi joriy ijro kontekstini eslab qoladi.

Bu yerda biz xuddi shu funktsiyani pow deb ataymiz, ammo bu mutlaqo muhim emas. Jarayon barcha funktsiyalar uchun bir xil:

1. Joriy kontekst stekning yuqori qismida “eslab qolinadi”.
2. Subchaqiruv uchun yangi kontekst yaratilinadi.
3. Subchaqiruv tugagandan so’ng – avvalgi kontekst stekdan chiqadi va uning bajarilishi davom etadi.

pow(2, 2) subchaqiruvga kirganimizda kontekst to’plami:

• Kontekst: { x: 2, n: 2, 1-satrda}