Рекурсія та стек

Давайте повернемося до функцій і вивчимо їх більш поглиблено.

Нашою першою темою буде рекурсія.

Якщо ви не новачок в програмуванні, то, мабуть, знайомі з рекурсією, і можете пропустити цю главу.

Рекурсія – це паттерн, який є корисним у ситуаціях, коли завдання може бути розділено на кілька завдань того ж роду, але простіших. Або коли завдання може бути спрощене до простої дії плюс простіший варіант того ж завдання. Або, як ми побачимо найближчим часом, щоб працювати з певними структурами даних.

Коли функція вирішує завдання, у процесі вона може викликати багато інших функцій. Частковий випадок цього є те, коли функція викликає себе. Це називається рекурсія.

Два способи мислення

Щоб почати з чогось простого – давайте напишемо функцію pow(x, n), що приводить x в натуральну степінь n. Іншими словами, множить x сам на себе n разів.

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

Існує два способи реалізації цього.

1. Ітеративне мислення: цикл for:

   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

2. Рекурсивне мислення: спростити завдання та викликати функцією саму себе:

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

Зверніть увагу, як рекурсивний варіант принципово відрізняється.

Коли pow(x, n) викликається, виконання розділяється на дві гілки:

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

1. Якщо n == 1, то все тривіально. Це називається база рекурсії, оскільки вона негайно виробляє очевидний результат: pow(x, 1) дорівнює x.
2. Інакше ми можемо представляти pow(x, n) як x * pow(x, n). У математиці можна написати xn = x * xn-1. Це називається рекурсивний крок: ми перетворюємо завдання на простішу дію (множення за допомогою x) та на простий виклик того ж завдання (pow з меншим n). Наступні кроки спрощують його далі і далі до n, що дорівнює 1.

Ми також можемо сказати, що pow рекурсивно викликає себе доn == 1.

Наприклад, для розрахунку pow(2, 4) рекурсивний варіант виконує ці кроки:

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

Отже, рекурсія робить виклик функції простішим, а потім – ще більш простішим, і так далі, доки результат стане очевидним.

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

Максимальна кількість вкладених викликів (включаючи перший) називається глибина рекурсії. У нашому випадку вона буде точно дорівнювати n.

Максимальна глибина рекурсії обмежена рушієм JavaScript. Ми можемо покластися, що вона може дорівнювати 10000, деякі рушії дозволяють отримати більшу глибину, але 100000, ймовірно, не підтримується більшістю з них. Є автоматичні оптимізації, які допомагають пом’якшити це (“оптимізація хвостових викликів”), але вони ще не підтримуються скрізь і працюють лише у простих випадках.

Це обмежує застосування рекурсії, але вона все ще залишається дуже широко поширеною. Є багато завдань, де рекурсивний спосіб мислення дає простіший код, який легше підтримувати.

Контекст виконання та стек

Тепер давайте розглянемо роботу рекурсивних викликів. Для цього ми подивимося під капот функцій.

Інформація про процес виконання викликаної функції зберігається у контексті виконання.

Контекст виконання – це внутрішня структура даних, яка містить деталі про виконання функції: де зараз керуючий потік, поточні змінні, значення this (ми не використовуємо його тут) і кілька інших внутрішніх деталей.

Один виклик функції має рівно один контекст виконання, пов’язаний з ним.

Коли функція робить вкладений виклик, відбувається наступне:

• Поточна функція зупиняється.
• Контекст виконання, пов’язаний з нею, запам’ятовується в спеціальній структурі даних, що називається стек контекстів виконання.
• Вкладений виклик виконується.
• Після закінчення, старий контекст виконання витягується з стека, і зовнішня функція відновлюється з того місця, де вона зупинилася.

Давайте подивимося, що відбувається під час виклику pow(2, 3).

pow(2, 3)

На початку виклику pow(2, 3) контекст виконання буде зберігати змінні: x = 2, n = 3, потік виконання знаходиться на рядку 1 функції.

Ми можемо намалювати його наступним чином:

• Контекст: {x: 2, n: 3, на рядку 1} pow(2, 3)

Ось тоді, функція починає виконуватися. Умова n == 1 – хибна, тому потік продовжується у другій гілці if:

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

alert( pow(2, 3) );

Змінні однакові, але виконання функції перейшло на інший рядок, тому контекст зараз:

• Контекст: {x: 2, n: 3, на рядку 5} pow(2, 3)

Для розрахунку x * pow(x, n - 1), ми повинні зробити підвиклик pow з новими аргументами pow(2, 2).

pow(2, 2)

Щоб зробити вкладений виклик, JavaScript пам’ятає контекст поточного виконання в стеці контексту виконання.

Тут ми викликаємо ту ж функцію pow, але це абсолютно не має значення. Цей процес однаковий для всіх функцій:

1. Поточний контекст “запам’ятовується” на вершині стека.
2. Новий контекст створюється для підвиклику.
3. Коли закінчиться підвиклик – попередній контекст дістається зі стека, і його виконання продовжується.

Ось контекстний стек, коли ми увійшли до підвиклику pow(2, 2):

• Контекст: {x: 2, n: 2, на рядку 1} pow(2, 2)
• Контекст: {x: 2, n: 3, на рядку 5} pow(2, 3)

Новий поточний контекст виконання знаходиться на вершині (виділений жирним шрифтом), а попередні контексти знаходяться в пам’яті нижче.

Коли ми закінчимо підвиклик, легко відновити попередній контекст, оскільки він зберігає як змінні, так і точне місце коду, де він зупинився.

pow(2, 1)

Процес повторюється: новий підвиклик здійснюється на рядку 5, тепер з аргументами x=2, n=1.

Створено новий контекст виконання, попередній витиснуто на вершину стека:

• Контекст: {x: 2, n: 1, на рядку 1} pow(2, 1)
• Контекст: {x: 2, n: 2, на рядку 5} pow(2, 2)
• Контекст: {x: 2, n: 3, на рядку 5} pow(2, 3)

Зараз існує 2 старі контексти і 1 зараз працює для pow(2, 1).

Вихід

Під час виконання pow(2, 1), умова n==1 – істинна, на відміну того, що було раніше, тому перша гілка виконує if:

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

Немає більше вкладених викликів, тому функція закінчується, повертаючи 2.

Оскільки функція завершується, то контекст виконання більше не потрібний, тому він видаляється з пам’яті. Попередній контекст відновлюється з вершини стека:

• Контекст: {x: 2, n: 2, на рядку 5} pow(2, 2)
• Контекст: {x: 2, n: 3, на рядку 5} pow(2, 3)

Виконання pow(2, 2) відновлено. Воно має результат підвиклику pow(2, 1), тому воно також може закінчити розрахунок x * pow(x, n - 1), повернувши 4.

Після цього відновлюється попередній контекст:

• Контекст: {x: 2, n: 3, на рядку 5} pow(2, 3)

Коли він закінчується, ми маємо результат pow(2, 3) = 8.

Глибина рекурсії в цьому випадку була: 3.

Як ми бачимо з наведених вище ілюстрацій, глибина рекурсії дорівнює максимальній кількості контексту у стеці.

Зверніть увагу на вимоги до пам’яті. Зберігання контекстів потребує пам’яті. У нашому випадку, підведення до степеня n фактично вимагає пам’яті для n контекстів, для всіх значень, що нижче n.

Алгоритм на основі циклу економить більше пам’яті:

function pow(x, n) {
  let result = 1;

  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

Ітеративний pow використовує єдиний контекст, змінюючи i and result у процесі. Його вимоги до пам’яті невеликі, фіксовані та не залежать від n.

Будь-яка рекурсія може бути переписана за допомогою циклу. Варіант з використанням циклу зазвичай може бути більш ефективним.

…Але іноді переписати рішення на цикл нетривіально, особливо коли функція використовує різні рекурсивні підвиклики залежно від умов та поєднує їх результат або коли розгалуження є більш складним. Тому така оптимізація може бути непотрібна і повністю не варта зусиль.

Рекурсія може дати коротший код, який легше зрозуміти та підтримувати. Оптимізація не потрібна в кожному місці, в основному нам потрібний хороший код, тому використовується рекурсія.

Рекурсивний обхід

Ще одним чудовим застосування рекурсії є рекурсивний обхід.

Уявіть, у нас є компанія. Структура персоналу може бути представлена як об’єкт:

let company = {
  sales: [{
    name: 'Іван',
    salary: 1000
  }, {
    name: 'Аліса',
    salary: 1600
  }],

  development: {
    sites: [{
      name: 'Петро',
      salary: 2000
    }, {
      name: 'Олександр',
      salary: 1800
    }],

    internals: [{
      name: 'Евген',
      salary: 1300
    }]
  }
};

Іншими словами, компанія має відділи.

• Відділи можуть мати масив персоналу. Наприклад, відділ продажу має 2 співробітника: Іван та Аліса.

• Або відділ може бути розділеним на підрозділи, наприклад, development має дві гілки: sites та internals. Кожна з них має свій персонал.

• Можливо також, що коли відділ зростає, він розділяється на субвідділи (або команди).

  Наприклад, відділ sites у майбутньому може бути розділений на команди для siteA і siteB. І вони, потенційно, можуть бути розділені в подальшому. Це не зображено на малюнку, просто слід мати це на увазі.

Тепер припустимо, що ми хочемо, щоб функція отримала суму всіх зарплат. Як ми можемо це зробити?

Ітеративний підхід нелегкий, тому що структура не проста. Перша ідея може полягати в тому, щоб зробити for цикл через company з вкладеним підциклами через 1-ий рівень відділів. Але тоді нам потрібно більше вкладених циклів, щоб ітеруватися через персонал у 2-му рівні, такому як sites… А потім ще один підцикл всередині них для 3-го рівня, який міг би з’явитися в майбутньому? Якщо ми поставимо 3-4 вкладені цикли у коді, щоб пройти один об’єкт, це стає досить потворним.

Давайте спробуємо рекурсію.

Як ми бачимо, коли наша функція отримує відділ для підрахунку суми зарплат, є два можливі випадки:

1. Або це “простий” відділ з масивом людей – тоді ми можемо підсумувати зарплату в простому циклі.
2. Або це об’єкт з n підвідділами – тоді ми можемо зробити n рекурсивних викликів, щоб отримати суму для кожного з підвідділів та поєднати результати.

1-й випадок є базою рекурсії, тривіальним випадком, коли ми отримуємо масив.

2-й випадок, коли ми отримуємо об’єкт, – це рекурсивний крок. Комплексне завдання розділяється на підзадачі для менших відділів. Вони в свою чергу можуть знову поділятися на підвідділи, але рано чи пізно поділ закінчиться і зведеться до випадку (1).

Алгоритм, мабуть, навіть легше читати у вигляді коду:

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}]
  }
};

// Функція для підрахунку суми зарплат
function sumSalaries(department) {
  if (Array.isArray(department)) { // випадок (1)
    return department.reduce((prev, current) => prev + current.salary, 0); // сума масиву
  } else { // випадок (2)
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // рекурсивно викликається для підвідділів, суммуючи результат
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 7700

Код короткий і його легко зрозуміти (сподіваюся?). Це сила рекурсії. Він також працює для будь-якого рівня вкладеного підвідділу.

Ось діаграма викликів:

Ми можемо легко побачити принцип: для об’єкта {...} зроблені підвиклики, а масиви[…]` – “листя” рекурсійного дерева, вони дають негайний результат.

Зауважте, що код використовує розумні функції, які ми розглянули раніше:

• Метод arr.reduce пояснено в розділі Методи масивів, щоб отримати суму масиву.
• Цикл for(val of Object.values(obj)) для ітерування значень об’єкта: Object.values повертає їх масив.

Рекурсивні структури

Рекурсивна (рекурсивно визначена) структура даних є структурою, яка повторює себе в своїх частинах.

Ми тільки що бачили це вище на прикладі структури компанії.

Відділ компанії це:

• Або масив людей.
• Або об’єкт з відділами.

Для веб-розробників набагато краще відомі приклади: HTML та XML-документи.

У HTML-документі HTML-тег може містити список:

• частини тексту.
• HTML-коментарі.
• Інших HTML-тегів (що, у свою чергу, можуть містити частини тексту/коментарі або інші теги тощо).

Це ще одне рекурсивне визначення.

Для кращого розуміння ми розглянемо ще одну рекурсивну структуру “Зв’язаний список”, який може бути кращою альтернативою для масивів у деяких випадках.

Зв’язаний список

Уявіть, що ми хочемо зберегти впорядкований список об’єктів.

Очевидним вибором буде масивом:

let arr = [obj1, obj2, obj3];

…Але є проблема з масивами. Операції “видалити елемент” та “вставити елемент” – дорогі. Наприклад, операція arr.unshift(obj) повинна мати справу зі всіма елементами, щоб звільнити місце для нового obj і, якщо масив великий, це вимагає часу. Те ж саме з arr.shift().

Єдині структурні модифікації, які не потребують масової перенумерації об’єктів, є ті, які працюють з кінцем масиву: arr.push/pop. Таким чином, масив може бути досить повільним для великих черг, коли ми повинні працювати з його початком.

Крім того, якщо нам дійсно потрібна швидка вставка/видалення, ми можемо вибрати іншу структуру даних, яка називається зв’язаний список.

Елемент зв’язаного списку рекурсивно визначається як об’єкт з:

• value.
• next властивість, що посилається на наступний елемент зв’язаного списку або null, якщо це кінець.

Наприклад:

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

Графічне представлення списку:

Альтернативний код для створення:

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;

Тут ми можемо ще більш чітко бачити, що є декілька об’єктів, кожен з яких має value та next, що вказуює на сусіда. Змінна list – це перший об’єкт у ланцюжку, тому слідуючи вказівникам next з неї ми можемо досягти будь-якого елемента.

Список можна легко розділити на декілька частин, а пізніше з’єднати знову:

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

To join:

list.next.next = secondList;

І, безумовно, ми можемо вставити або видалити елементи в будь-якому місці.

Наприклад, для підготовки нового значення, нам потрібно оновити голову списку:

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

// додавання нового значення до списку
list = { value: "new item", next: list };

Щоб видалити значення з середини, змінити next попереднього:

list.next = list.next.next;

Ми зробили list.next стрибає через 1 на значення 2. Значення 1 зараз виключається з ланцюга. Якщо воно не зберігається ніде, то воно буде автоматично видалено з пам’яті.

На відміну від масивів, немає массових перенумерацій, ми можемо легко переставляти елементи.

Звичайно, списки не завжди краще, ніж масиви. Інакше кожен буде використовувати лише списки.

Основний недолік полягає в тому, що ми не можемо легко отримати доступ до елемента за його номером. У масиві це легко: arr[n] є прямим посиланням. А в списку ми повинні почати з першого елемента і піти next N разів, щоб отримати n-ий елемент.

…Але ми не завжди потребуємо таких операцій. Наприклад, коли нам потрібна черга або навіть двобічна черга – упорядкована структура, яка повинна дозволити дуже швидко додавати/видаляти елементи з обох кінців, але доступ до середини не потрібний.

Списки можуть бути покращені:

• Ми можемо додати властивість prev на доповнення до next, для посилання на попередній елемент, щоб легко переміщатися.
• Ми також можемо додати змінну названу tail, що посилається на останній елемент списку (і оновлювати його при додаванні/видалення елементів з кінця).
• …Структура даних може відрізнятися залежно від наших потреб.

Підсумки

Терміни:

• Рекурсія це термін програмування, який означає, що функція викликає саму себе. Рекурсивні функції можуть бути використані для вирішення завдань у елегантний спосіб.

  Коли функція викликає себе, це називається рекурсійний крок. База рекурсії є функціональними аргументами, які роблять завдання таким простим, що функція не робить додаткових викликів.

• Рекурсивно визначена структура даних – це структура даних, яка може бути визначена, з використанням самої себе.

  Наприклад, зв’язаний список може бути визначений як структура даних, що складається з об’єкта, що посилається на список (або null).

  list = { value, next -> list }

  Дерева, такі як HTML-елементи або дерево відділів з цієї глави, також є рекурсивними: вони розгалужуються та кожна гілка може мати інші гілки.

  Рекурсивні функції можуть бути використані для того, щоб пройти їх, як ми бачили у прикладі sumSalary.

Будь-яка рекурсивна функція може бути переписана в ітераційну. І це іноді потрібно для оптимізації. Але для багатьох завдань рекурсивне рішення досить швидке і його легше написати та підтримувати.