Recursion va stack

Rekursiya va stack

Keling, funksiyalarni yana chuqurroq o‘rganamiz.

Bizning birinchi mavzu rekursiya haqida bo‘ladi.

Agar siz dasturlash bilan tanish bo'lsangiz, ehtimol rekursiya haqida eshitgansiz va bu bo'limni o'tkazib yuborsangiz ham bo‘ladi.

Rekursiya — bu dasturlashning bir usuli bo‘lib, vazifa tabiiy ravishda o‘zidan kichikroq va oddiyroq bo‘lgan bir nechta vazifalarga bo‘linishi mumkin bo'lgan holatlarda foydali. Yoki biror vazifani oddiyroq amal va shunga o'xshash kichikroq vazifaga aylantirish mumkin bo‘lsa. Yoki ba'zi ma'lumot tuzilmalarini boshqarish uchun ishlatiladi.

Bir funksiya vazifani bajarayotganda, boshqa ko'plab funksiyalarni chaqirishi mumkin. Buning qisman ko'rinishi — bu funksiya o‘zini o‘zi chaqirishi. Bu jarayon rekursiya deb ataladi.

Ikki xil yondashuv

Boshlanish uchun oddiy bir misolni ko‘raylik: pow(x, n) funksiyasini yozamiz, bu x sonini n darajaga ko‘taradi. Boshqacha aytganda, x sonini n marta o‘zi bilan ko‘paytiradi.

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

Bu ikkita yo‘l bilan amalga oshirilishi mumkin.

Iterativ usul: for sikli orqali:

function pow(x, n) {
  let result = 1;
 
  // `x` ni `n` marta ko‘paytirish
  for (let i = 0; i < n; i++) {
    result *= x;
  }
 
  return result;
}
 
console.log(pow(2, 3)); // 8

Rekursiv usul: vazifani oddiyroq qilib chaqirish:

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

Diqqat qiling, rekursiv yondashuvning asosiy farqi bor.

pow(x, n) chaqirilganda, bajarish ikki shoxga bo‘linadi:

             n==1 bo'lsa:    = x
            /
pow(x, n) =
            \
             else bo‘lsa:    = x * pow(x, n - 1)

Agar n == 1 bo‘lsa, hammasi oddiy. Bu rekursiyaning asosi deb ataladi, chunki bu darhol tushunarli natija beradi: pow(x, 1) natijasi x bo‘ladi.

Aks holda, biz pow(x, n) ni x * pow(x, n - 1) deb ifodalashimiz mumkin. Matematikada bu quyidagicha yoziladi: x^n = x * x^(n-1). Bu rekursiv qadam deb ataladi: vazifa oddiyroq amalga (ko‘paytirish x ga) va xuddi shu vazifaning oddiyroq chaqiruviga (kichikroq n bilan pow) aylanadi. Keyingi qadamlar uni soddalashtiradi va oxir-oqibat n 1 ga tenglashgunga qadar davom etadi.

Misol uchun, pow(2, 4) ni hisoblash uchun rekursiv yondashuv quyidagi qadamlarni amalga oshiradi:

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

Shunday qilib, rekursiya funktsiya chaqiruvini oddiyroq biriga qisqartiradi va natija tushunarli bo‘lguncha bu jarayon davom etadi.

Rekursiya odatda qisqaroq bo‘ladi

Rekursiv yechim odatda iterativdan qisqaroq bo‘ladi.

Biz shu yerda if o‘rniga shartli operator ? ni ishlatib, kodni qisqartirishimiz va o‘qilishi oson bo‘lishi uchun pow(x, n) funksiyasini qayta yozishimiz mumkin:

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

Ichki chaqiruvlar maksimal soni (shu jumladan birinchisi) rekursiya chuqurligi deb ataladi. Bizning holatda, u aniq n bo'ladi.

Maksimal rekursiya chuqurligi JavaScript dvigateli tomonidan cheklangan. Biz uning 10000 ekanligiga ishonishimiz mumkin, ba'zi dvigatellar ko'proq ruxsat beradi, lekin 100000 ularning aksariyati uchun chegaradan tashqarida. Buni engillashtirishga yordam beradigan avtomatik optimallashtirishlar ("quyruq qo'ng'iroqlarini optimallashtirish") mavjud, ammo ular hali hamma joyda qo'llab-quvvatlanmaydi va faqat oddiy holatlarda ishlaydi.

Bu rekursiyani qo'llashni cheklaydi, lekin u hali ham juda keng bo'lib qolmoqda. Ko'pgina vazifalar mavjud bo'lib, ularda rekursiv fikrlash usuli oddiyroq kodni beradi, uni saqlash osonroq.

Rekursiya chuqurligi

Rekursiya chuqurligi (ilk chaqiruvni hisobga olgan holda) maksimal chaqiruvlar soni deb ataladi. Bizning holatimizda bu aniq n ga teng bo'ladi.

JavaScript dvigateli maksimal rekursiya chuqurligini cheklaydi. Biz 10000 ga tayanishimiz mumkin, ayrim dvigatellar ko'proq ruxsat beradi, ammo 100000 ko'pgina dvigatellarda chegaradan tashqarida. Avtomatik optimizatsiyalar mavjud bo'lib, ular ("qo'shni chaqiruvlarni optimallashtirish") yordam beradi, ammo ular hali ham barcha joylarda qo'llanilmaydi va faqat oddiy holatlarda ishlaydi.

Bu rekursiyani qo'llash imkoniyatini cheklaydi, ammo bu hali ham juda keng. Ko'p vazifalar mavjud bo'lib, rekursiv yondashuv sodda kod, oson qo'llab-quvvatlash uchun imkon beradi.

Ijro konteksti va stek

Endi rekursiv chaqiruvlar qanday ishlashini ko'rib chiqamiz. Buning uchun funksiyalar ostida qanday ishlashini ko'rib chiqamiz.

Ijro konteksti – bu funksiyaning ijrosiga oid ma'lumotlarni saqlovchi ichki ma'lumotlar tuzilmasidir: hozirgi boshqaruv oqimi, joriy o'zgaruvchilar, this qiymati (bu yerda biz foydalanmaymiz) va boshqa ba'zi ichki tafsilotlar.

Har bir funktsiya chaqiruvi bir dona ijro kontekstiga ega bo'ladi.

Funksiya boshqa bir chaqiruvni amalga oshirsa, quyidagilar sodir bo'ladi:

• Joriy funksiya to'xtatiladi.
• U bilan bog'liq ijro konteksti ijro konteksti stekiga maxsus ma'lumotlar tuzilmasida saqlanadi.
• Yangi chaqiruv bajariladi.
• Tugallangandan so'ng, eski ijro konteksti stekdan qaytariladi va tashqi funksiya to'xtagan joyidan davom ettiriladi.

Keling, pow(2, 3) chaqiruvi vaqtida nima bo'lishini ko'rib chiqamiz.

pow(2, 3)

pow(2, 3) chaqirig'ida ijro konteksti quyidagilarni saqlaydi: x = 2, n = 3, ijro oqimi funktsiyaning 1-qatorida.

Buni quyidagicha tasvirlash mumkin:

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

Funksiya bajarila boshlaganda, n == 1 sharti noto'g'ri bo'lib, if shartidan keyingi bo'limga o'tiladi:

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

O'zgaruvchilar bir xil, ammo qator o'zgaradi, shuning uchun kontekst endi quyidagicha bo'ladi:

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

x * pow(x, n - 1) hisoblash uchun pow(2, 2) bilan yangi chaqiruvni amalga oshirish kerak.

pow(2, 2)

Yangi chaqiruvni amalga oshirish uchun, JavaScript joriy ijro kontekstini ijro konteksti stekida eslab qoladi.

Bu yerda pow funksiyasi chaqirilmoqda, lekin jarayon barcha funksiyalar uchun bir xil:

• Joriy kontekst stekning eng yuqori qismiga saqlanadi.
• Yangi kontekst yangi chaqiruv uchun yaratiladi.
• Yangi chaqiruv tugallangandan so'ng, oldingi kontekst stekdan chiqariladi va uning ijrosi davom ettiriladi.

Yangi chaqiruv pow(2, 2) chaqiruvi vaqtida kontekst stek quyidagicha bo'ladi:

Kontekst: { x: 2, n: 2, 1-qator } pow(2, 2)
Kontekst: { x: 2, n: 3, 5-qator } pow(2, 3)

Yangi joriy ijro konteksti yuqorida (va qalin) bo'lib, oldingi eslab qolingan kontekstlar pastda.

Yangi chaqiruv tugagandan so'ng – oldingi kontekstni tiklash oson, chunki u ikkala o'zgaruvchilarni va kodning to'xtagan joyini saqlaydi.

pow(2, 1)

Jarayon davom etadi: yangi chaqiruv 5-qator bo'ylab, endi x=2, n=1 argumentlari bilan amalga oshiriladi.

Yangi ijro konteksti yaratiladi, oldingi kontekst stekning eng yuqori qismiga qo'shiladi:

Kontekst: { x: 2, n: 1, 1-qator } pow(2, 1)
Kontekst: { x: 2, n: 2, 5-qator } pow(2, 2)
Kontekst: { x: 2, n: 3, 5-qator } pow(2, 3)

Hozirda ikkita eski kontekst va 1 joriy ijro konteksti bor.

Yakun

pow(2, 1) ijro etilganida, n == 1 sharti to'g'ri bo'lgani uchun if shartining birinchi tarmog'i ishlaydi:

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

Boshqa chaqiruvlar endi yo'q, shuning uchun funksiya tugaydi va 2 ni qaytaradi.

Funksiya tugagandan so'ng, uning ijro konteksti endi kerak emas, shuning uchun xotiradan o'chiriladi. Oldingi kontekst qaytariladi:

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

pow(2, 2) ijrosi davom etadi. Bu chaqiruv pow(2, 1) natijasini oladi, shuning uchun x * pow(x, n - 1) hisoblanadi va 4 qaytariladi.

Keyin oldingi kontekst qaytariladi:

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

pow(2, 3) tugaydi va natija pow(2, 3) = 8 bo'ladi.

Bu holatda rekursiya chuqurligi: 3.

Ijro kontekstlari xotira talab qiladi. Bizning holatda n uchun ijro kontekstlar talab qilinadi, barcha kichikroq n qiymatlari uchun.

Takrorlanuvchi algoritm ko'proq xotira talab qiladi:

function pow(x, n) {
  let result = 1;
 
  for (let i = 0; i < n; i++) {
    result *= x;
  }
 
  return result;
}

Iterativ pow bir dona kontekstni ishlatadi, i va result qiymatlarini o'zgartiradi. Uning xotira talab qilinishi kichik, o'zgarmas va n ga bog'liq emas.

Har qanday rekursiya siklga o'zgartirilishi mumkin. Sikl variantini odatda samaraliroq qilish mumkin.

Lekin ba'zida o'zgartirish qiyin bo'lishi mumkin, ayniqsa funktsiya shartlarga qarab turli rekursiv chaqiruvlarni ishlatsa va ularning natijalarini birlashtirsa yoki shartlar yanada murakkab bo'lsa. Va optimallashtirish kerak emas, bu ko'p hollarda yaxshi kod kerak bo'ladi, shuning uchun rekursiya ishlatiladi.

Rekursiv ko'rsatmalar

Yana bir katta qo'llanilishi – rekursiv ko'rsatmalar.

Tasavvur qiling, bizda kompaniya bor. Xodimlar tuzilmasi ob'ekt sifatida taqdim etiladi:

let company = {
  sales: [
    {
      name: 'John',
 
      salary: 1000,
    },
    {
      name: 'Alice',
      salary: 1600,
    },
  ],
 
  development: {
    sites: [
      {
        name: 'Peter',
        salary: 2000,
      },
      {
        name: 'Alex',
        salary: 1800,
      },
    ],
 
    internals: [
      {
        name: 'Jack',
        salary: 1300,
      },
    ],
  },
};

Boshqacha qilib aytganda, kompaniyada bo'limlar mavjud.

Bir bo'lim xodimlar massiviga ega bo'lishi mumkin. Masalan, savdo bo'limida 2 xodim bor: John va Alice.

Yoki bo'lim subbo'limlarga bo'linishi mumkin, masalan, rivojlanish bo'limi ikkita tarmoqqa ega: saytlar va ichki bo'limlar. Har birida o'z xodimlari bor.

Shuningdek, subbo'lim o'sishi bilan, u subsubbo'limlarga (yoki jamoalarga) bo'linishi mumkin.

Masalan, saytlar bo'limi kelajakda saytA va saytB jamoalariga bo'linishi mumkin. Va ular, ehtimol, yana bo'linishi mumkin. Bu tasvirda yo'q, shunchaki yodda tutish uchun.

Endi barcha maoshlarning summasini olish uchun funksiya yozmoqchi bo'lsak, qanday qilishimiz mumkin?

Iterativ yondashuv qiyin, chunki tuzilma oddiy emas. Birinchi g'oya kompaniya bo'ylab for siklni amalga oshirish va birinchi darajadagi bo'limlar bo'yicha ichki siklni amalga oshirish bo'lishi mumkin. Ammo keyin bizga 2-darajadagi bo'limlar kabi xodimlarni takrorlash uchun ko'proq ichki sikllar kerak bo'ladi... Va keyingi darajadagi bo'limlar bo'lishi mumkin. Agar kodga 3-4 ichki sikl qo'shsak, u juda murakkab bo'ladi.

Keling, rekursiya orqali sinab ko'ramiz.

Bizning funksiyamiz bo'limni yig'ish uchun ikki holat mavjud:

1. Bu "oddiy" bo'lim bo'lib, xodimlar massivini o'z ichiga oladi – shunda biz maoshlarni oddiy siklda yig'ishimiz mumkin.
2. Yoki bu ob'ekt bo'lib, N ta subbo'limlarga ega – shunda biz har bir subbo'lim uchun rekursiv chaqiruvlar amalga oshirib, natijalarni birlashtiramiz.

1-hol rekursiyaning asosiy holati, massivni olish uchun oddiy holatdir.

2-hol, ob'ektni olishda, rekursiv qadamdir. Murakkab vazifa kichikroq bo'limlarga bo'linadi. Ular yana bo'linishi mumkin, lekin oxir-oqibat bo'linish (1) da tugaydi.

Algoritm koddan o'qish osonroq bo'lishi mumkin:

let company = {
  // bir xil ob'ekt, qisqartirilgan
  sales: [
    { name: 'John', salary: 1000 },
    { name: 'Alice', salary: 1600 },
  ],
  development: {
    sites: [
      { name: 'Peter', salary: 2000 },
      { name: 'Alex', salary: 1800 },
    ],
    internals: [{ name: 'Jack', salary: 1300 }],
  },
};
 
// Ishni bajaruvchi funksiya
function sumSalaries(department) {
  if (Array.isArray(department)) {
    // holat (1)
    return department.reduce((prev, current) => prev + current.salary, 0); // massivni yig'ish
  } else {
    // holat (2)
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // subbo'limlar uchun rekursiv chaqiruvlar, natijalarni yig'ish
    }
    return sum;
  }
}
 
alert(sumSalaries(company)); // 7700

Kod qisqa va o'qilishi oson (umid qilamanki?). Bu rekursiyaning qudrati. U har qanday darajadagi subbo'limlar o'z ichiga olgan struktura uchun ishlaydi.

Biz prinsipni osonlik bilan ko'rishimiz mumkin: ob'ektlar {...} uchun subchaqiruvlar amalga oshiriladi, aksincha massivlar [...] rekursiya daraxtining "barglari" bo'lib, ular darhol natija beradi.

Kod avvalroq ko'rib chiqqan aqlli xususiyatlardan foydalanadi:

• Massivning yig'indisini olish uchun arr.reduce metodidan foydalanilgan, bu Array metodlari bo'limida tushuntirilgan.
• Ob'ekt qiymatlarini takrorlash uchun for(val of Object.values(obj)) siklidagi Object.values metodidan foydalanilgan, bu metod ob'ekt qiymatlarini o'z ichiga olgan massivni qaytaradi.

Rekursiv tuzilmalar

Rekursiv (rekursiv-tariflangan) ma'lumotlar tuzilmasi — bu o'z qismlarida o'zini takrorlaydigan tuzilma.

Yuqaridagi kompaniya strukturasining misolida bu tushunchani ko'rdik.

Kompaniya bo'limi:

• Yoki odamlar massivi.
• Yoki bo'limlardan iborat ob'ekt.

Veb-dasturchilar uchun tanishroq misollar mavjud: HTML va XML hujjatlari.

HTML hujjatida HTML-teg quyidagi narsalarni o'z ichiga olishi mumkin:

• Matn bo'laklari.
• HTML-kommentariyalar.
• Boshqa HTML-teglar (ular matn bo'laklarini/commentarlarni yoki boshqa teglarni o'z ichiga olishi mumkin va hokazo).

Bu yana bir marta rekursiv ta'rifdir.

Yaxshi tushunish uchun, boshqa bir rekursiv tuzilma bo'lgan “Bog'langan ro'yxat”ni ko'rib chiqamiz, bu ba'zi hollarda massivlar uchun yaxshiroq alternativa bo'lishi mumkin.

Bog'langan ro'yxat

Tasavvur qiling, biz obyektlarning tartiblangan ro'yxatini saqlamoqchimiz.

Tabiiy tanlov — massiv:

let arr = [obj1, obj2, obj3];

…Lekin massivlar bilan bog'liq muammo bor. “Elementni o'chirish” va “element qo'shish” operatsiyalari qimmatga tushadi. Masalan, arr.unshift(obj) operatsiyasi yangi obj uchun joy yaratish uchun barcha elementlarni qayta raqamlaydi va agar massiv katta bo'lsa, bu vaqt oladi. arr.shift() bilan ham shunday.

Massivning faqat oxirida amalga oshiriladigan strukturaviy o'zgarishlar massaviy qayta raqamlanishni talab qilmaydi: arr.push/pop. Shuning uchun katta navbatlar uchun massiv juda sekin bo'lishi mumkin, agar biz boshida ishlashimiz kerak bo'lsa.

Boshqa tomondan, agar biz tez qo'shish/o'chirishni haqiqatdan ham talab qilsak, bog'langan ro'yxat deb ataladigan boshqa ma'lumotlar tuzilmasini tanlashimiz mumkin.

Bog'langan ro'yxat elementi quyidagi tarzda rekursiv tarzda ta'riflanadi:

• value.
• next xossasi keyingi bog'langan ro'yxat elementiga yoki bu oxir bo'lsa nullga ishora qiladi.

Masalan:

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null,
      },
    },
  },
};

Ro'yxatning grafik tasviri:

Alternativ kod yaratish uchun

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };
list.next.next.next.next = null;

Bu yerda aniqroq ko'rishimiz mumkin bo'lgan narsa shundaki, bir nechta ob'ektlar mavjud, har biri value va qo'shni ob'ektga ishora qiluvchi next xossasiga ega. list o'zgaruvchisi zanjirdagi birinchi ob'ekt, shuning uchun next ko'rsatkichlari orqali har qanday elementga yetib borishimiz mumkin.

Ro'yxatni osonlik bilan bir nechta qismlarga ajratish va keyin qayta birlashtirish mumkin:

let secondList = list.next.next;
list.next.next = null;

Qo'shish uchun

list.next.next = secondList;

Va albatta, biz har qanday joyga elementlarni qo'shish yoki olib tashlashimiz mumkin.

Masalan, yangi qiymat qo'shish uchun, ro'yxatning boshini yangilashimiz kerak:

let list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };
 
// Ro'yxatga yangi qiymat qo'shish
list = { value: 'new item', next: list };

Orta qismini olib tashlash uchun, avvalgi elementning next qiymatini yangilang:

list.next = list.next.next;

Biz list.next ni 1 ustidan o'tib, 2 qiymatiga o'tkazdik. Endi 1 qiymati zanjirdan chiqarildi. Agar boshqa joyda saqlanmasa, u avtomatik ravishda xotiradan o'chiriladi.

Massivlar bilan solishtirganda, bunda massa raqamlarini o'zgartirish yo'q, elementlarni osonlik bilan qayta tartiblash mumkin.

Tabiiyki, ro'yxatlar har doim massivlardan yaxshiroq emas. Aks holda, hamma faqat ro'yxatlardan foydalanar edi.

Asosiy kamchilik shundaki, elementni uning raqami bo'yicha osonlik bilan olish mumkin emas. Massivda bu oson: arr[n] to'g'ridan-to'g'ri murojaat. Lekin ro'yxatda biz birinchi elementdan boshlashimiz va N marta keyingi elementga o'tishimiz kerak bo'ladi, N-chi elementni olish uchun.

…Biroq, har doim bunday operatsiyalar kerak bo'lmaydi. Masalan, qator yoki hatto deque – elementlarni ikki uchidan juda tez qo'shish/olish imkoniyatiga ega bo'lgan tartiblangan struktura, lekin o'rtasidagi elementlarga murojaat qilish zarurati yo'q.

Ro'yxatlar takomillashtirilishi mumkin:

• Biz next ga qo'shimcha ravishda prev xususiyatini qo'shishimiz mumkin, bu avvalgi elementga osonlik bilan qaytishga yordam beradi.
• Shuningdek, oxirgi elementni ko'rsatuvchi tail nomli o'zgaruvchini qo'shishimiz mumkin (va elementlarni oxiridan qo'shish/olish vaqtida yangilash).

…Ma'lumotlar tuzilmasi ehtiyojlarimizga qarab farq qilishi mumkin.

Xulosa

Tushunchalar:

1. Rekursiya – bu funksiyani o'zidan chaqirishni anglatadigan dasturlash atamasi. Rekursiv funksiyalar vazifalarni estetik yo'llar bilan hal qilish uchun ishlatilishi mumkin.

2. Funksiya o'zini chaqirsa, bu rekursiya bosqichi deb ataladi. Rekursiyaning asosiy tamoyili shundaki, funksiya argumentlari vazifani juda oddiy qiladi, shunda funksiya qo'shimcha chaqiriqlar qilmaydi.

3. Rekursiv ta'riflangan ma'lumotlar tuzilmasi – bu o'zini ishlatib ta'riflanishi mumkin bo'lgan ma'lumotlar tuzilmasidir.

Masalan, bog'langan ro'yxat o'zini ro'yxatga (yoki null) havola qiluvchi obyekt sifatida ta'riflanishi mumkin:

list = { value, next -> list }

1. HTML elementlari daraxti yoki ushbu bobdagi bo'limlar daraxti kabi daraxtlar ham tabiiy ravishda rekursivdir: ular shoxlarga ega va har bir shox boshqa shoxlarga ega bo'lishi mumkin.

2. Rekursiv funksiyalar ulardan yurish uchun ishlatilishi mumkin, bu biz sumSalary misolida ko'rdik.

3. Har qanday rekursiv funksiya iterativ funksiya sifatida qayta yozilishi mumkin. Va bu ba'zan optimallashtirish uchun talab qilinadi. Ammo ko'plab vazifalar uchun rekursiv yechim yetarli tez va yozish va qo'llab-quvvatlash uchun osonroq.