8 квітня 2024 р.

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

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

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

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

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

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

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

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

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

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

Ітеративне мислення: цикл 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

Рекурсивне мислення: спростити завдання та викликати функцією саму себе:
```
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)
        

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

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

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

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

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

Рекурсивне рішення, як правило, коротше, ніж ітераційне.

Ми можемо переписати те ж саме, використовуючи умовний оператор ? замість if, щоб зробити pow(x, n) більш лаконічним і зберегти легкість читання:

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, але це абсолютно не має значення. Цей процес однаковий для всіх функцій:

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

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

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

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

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

Тут, на малюнку, ми використовуємо “на рядку”, так як у нашому прикладі є лише один підвиклик в рядку, але, як правило, один рядок коду може містити декілька підвикликів, як pow(…) + pow(…) + somethingElse(…).

Тому було б точніше сказати, що виконання продовжується “відразу після підвиклику”.

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 вкладені цикли у коді, щоб пройти один об’єкт, це стає досить потворним.

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

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

Або це “простий” відділ з масивом людей – тоді ми можемо підсумувати зарплату в простому циклі.
Або це об’єкт з 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.

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

Завдання

Сума всіх чисел до даного

Напишіть функцію sumTo(n), що обчислює суму чисел 1 + 2 + ... + n.

Наприклад:

          sumTo(1) = 1
sumTo(2) = 2 + 1 = 3
sumTo(3) = 3 + 2 + 1 = 6
sumTo(4) = 4 + 3 + 2 + 1 = 10
...
sumTo(100) = 100 + 99 + ... + 2 + 1 = 5050
        

Зробити 3 варіанти рішення:

Використання циклу.
Використання рекурсії, у випадку sumTo(n) = n + sumTo(n-1) для n > 1.
Використання формули арифметичної прогресії.

Приклад результату:

          function sumTo(n) { /*... ваш код ... */ }

alert( sumTo(100) ); // 5050

P.S. Який варіант рішення є найшвидшим? Найповільнішим? Чому?

P.P.S. Чи можемо ми використовувати рекурсію для підрахунку sumTo(100000)?

Рішення з використанням циклу:

function sumTo(n) {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
}

alert( sumTo(100) );

Рішення з використанням рекурсії:

function sumTo(n) {
  if (n == 1) return 1;
  return n + sumTo(n - 1);
}

alert( sumTo(100) );

Рішення з використанням формули: sumTo(n) = n*(n+1)/2:

function sumTo(n) {
  return n * (n + 1) / 2;
}

alert( sumTo(100) );

P.S. Звичайно, формула є найшвидшим рішенням. Вона використовує лише 3 операції для будь-якого числа n. Математика допомагає!

Варіант з циклом є другим з точки зору швидкості. Як і у випадку рекурсії, в циклі ми сумуємо ті ж числа. Але рекурсія передбачає вкладені виклики та управління стеком. Це також займає ресурси, тому це повільніше.

P.P.S. Деякі рушії підтримують оптимізацію “хвостового виклику” (“tail call”): якщо рекурсивний виклик є останнім в функції, то зовнішня функція не повинна відновлювати виконання, отже рушію не потрібно запам’ятовувати контекст виконання. Це зменшує використання пам’яті. Але якщо рушій JavaScript не підтримує оптимізацію хвостового виклику (більшість з них не підтримує), то виникне помилка: максимальний розмір стека перевищиться, оскільки зазвичай є обмеження на загальний розмір стека.

Розрахувати факторіал

Факторіал з натурального числа – це число, помножене на "число мінус один", потім на "число мінус два" і так до 1. Факторіал n позначається як n!

Ми можемо написати визначення факторіалу наступним чином:

n! = n * (n - 1) * (n - 2) * ...*1

Значення факторіалів для різних n:

          1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120
        

Завдання полягає в тому, щоб написати функцію factorial(n), яка обчислює n! за допомогою рекурсивних викликів.

alert( factorial(5) ); // 120

P.S. Підказка: n! може бути записане як n * (n-1)!. Наприклад: 3! = 3*2! = 3*2*1! = 6

За визначенням, факторіал n! може бути записаний як n * (n-1)!.

Інакше кажучи, результат factorial(n) може бути розрахований, як n помножений на результат factorial(n-1). І виклик до n-1 може рекурсивно спускатися нижче та нижче, аж до 1.

function factorial(n) {
  return (n != 1) ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120

Базисом рекурсії є значення 1. Ми також можемо зробити 0 базисом, це не має великого значення, але дає ще один рекурсивний крок:

function factorial(n) {
  return n ? n * factorial(n - 1) : 1;
}

alert( factorial(5) ); // 120

Числа Фібоначчі

Послідовність чисел Фібоначчі має формулу F_n = F_n-1 + F_n-2. Іншими словами, наступне число є сумою двох попередніх.

Перші два числа: 1, потім 2(1+1), потім 3(1+2), 5(2+3) і так далі: 1, 1, 2, 3, 5, 8, 13, 21....

Числа Фібоначчі пов’язані із золотим перетином і багатьма природними явищами навколо нас.

Напишіть функцію fib(n), яка повертає n-th число Фібоначчі.

Приклад:

          function fib(n) { /* твій код */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757
        

P.S. Функція повинна бути швидкою. Виклик fib(77) має тривати не більше частки секунди.

Спершу ми можемо спробувати рекурсію.

Числа Фібоначчі є рекурсивними за визначенням:

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // екстремально повільно!

…Але для великих значень n це дуже повільно. Наприклад, fib(77) може заморозити роботу рушія на деякий час, споживаючи всі ресурси центрального процесора.

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

Наприклад, подивимось на уривок обчислень fib(5):

          ...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...
        

Тут ми спостерігаємо що значення fib(3) потрібне для обох fib(5) та fib(4). Тож fib(3) буде викликано два рази абсолютно незалежно.

Ось повне дерево рекурсії:

Ми можемо чітко простежити, що fib(3) вираховується двічі, а fib(2) – тричі. Загальна кількість обчислень росте набагато швидше, ніж n, що робить його величезним навіть для n=77.

Ми можемо оптимізувати це, запам’ятовуючи вже обчислені результати: якщо значення, скажімо, fib(3) обчислюється один раз, ми можемо просто повторно використовувати його в майбутніх обчисленнях.

Як інший варіант, ми можемо відмовитись від рекурсії та використати зовсім інший алгоритм на основі циклу.

Замість переходу від n до нижчих значень ми можемо створити цикл, який починається з 1 і 2, потім отримує fib(3) як їхню суму, а потім fib(4) як суму двох попередніх значень, потім fib(5) і йде вгору і вгору, поки не досягне потрібного значення. На кожному кроці нам потрібно лише запам’ятати два попередні значення.

Ось кроки нового алгоритму в деталях.

Початок:

          // a = fib(1), b = fib(2), ці значення типово дорівнюють одиниці
let a = 1, b = 1;

// get c = fib(3) як їх сума
let c = a + b;

/* тепер ми маємо fib(1), fib(2), fib(3)
a  b  c
1, 1, 2
*/
        

Тепер ми хочемо отримати fib(4) = fib(2) + fib(3).

Зсуньмо змінні: a,b і отримаємо fib(2),fib(3) та c отримає їх суму:

          a = b; // тепер a = fib(2)
b = c; // тепер b = fib(3)
c = a + b; // c = fib(4)

/* тепер ми маємо таку послідовність:
   a  b  c
1, 1, 2, 3
*/
        

Наступний крок дає нове число послідовності:

          a = b; // тепер a = fib(3)
b = c; // тепер b = fib(4)
c = a + b; // c = fib(5)

/* тепер послідовність така (на одне число більше):
      a  b  c
1, 1, 2, 3, 5
*/
        

…І так далі, поки не отримаємо потрібне значення. Це набагато швидше, ніж рекурсія, і не вимагає повторних обчислень.

Повний код:

function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

Цикл починається з i=3, тому що перше та друге значення послідовності жорстко закодовані в змінних a=1, b=1.

Підхід називається динамічне програмування знизу вгору.

Вивести одинозв’язаний список

Скажімо, у нас є одинозв’язаний список (як описано в розділі Рекурсія та стек):

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

Напишіть функцію printList(list), що виводить список елементів один за одним.

Зробіть два варіанти рішення: з використанням циклу та з використанням рекурсії.

Що краще: з рекурсією чи без неї?

Рішення на основі циклу

Варіант рішення на основі циклу:

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

function printList(list) {
  let tmp = list;

  while (tmp) {
    alert(tmp.value);
    tmp = tmp.next;
  }

}

printList(list);

Зверніть увагу, що ми використовуємо тимчасову змінну tmp, щоб пройти по списку. Технічно ми могли б використовувати замість нього параметр функції list:

          function printList(list) {

  while(list) {
    alert(list.value);
    list = list.next;
  }

}
        

…Але це було б нерозумно. У майбутньому нам доведеться розширити функцію, зробити щось інше з list. Якщо ми змінюємо list, то ми втрачаємо таку здатність.

Говорячи про хороші імена змінних, list тут – це сам список. Його перший елемент. І це повинно залишитися так. Це ясно і надійний.

З іншого боку, tmp використовується виключно проходу, як i у for циклі.

Рішення через рекурсію

Рекурсивний варіант printlist(list) слідує простій логіці: вивести список, який ми повинні вивести поточний елемент list, а потім зробити те ж саме дляlist.next:

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

function printList(list) {

  alert(list.value); // виведіть поточний елемент

  if (list.next) {
    printList(list.next); // зробіть те ж саме для решти списку
  }

}

printList(list);

Що ж тепер краще?

Технічно цикл є більш ефективним. Ці два варіанти роблять те ж саме, але цикл не витрачає ресурси для вкладених викликів.

З іншого боку, рекурсивний варіант коротший, а іноді його легше зрозуміти.

Вивести одинозв’язаний список у зворотному порядку

Виведіть одинозв’язаний список з попереднього завдання Вивести одинозв’язаний список у зворотному порядку.

Зробіть два рішення: за допомогою циклу та з використанням рекурсії.

Використання рекурсії

Тут рекурсивна логіка трохи складна.

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

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

function printReverseList(list) {

  if (list.next) {
    printReverseList(list.next);
  }

  alert(list.value);
}

printReverseList(list);

За допомогою циклу

Варіант з циклом також трохи складніший, ніж прямий вивід.

Немає можливості отримати останнє значення в нашому list. Ми також не можемо “повернутися назад”.

Отже, що ми можемо зробити, так це спочатку пройти елементи в прямому порядку і запам’ятати їх у масиві, а потім вивести те, що ми запам’ятали, в зворотному порядку:

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

function printReverseList(list) {
  let arr = [];
  let tmp = list;

  while (tmp) {
    arr.push(tmp.value);
    tmp = tmp.next;
  }

  for (let i = arr.length - 1; i >= 0; i--) {
    alert( arr[i] );
  }
}

printReverseList(list);

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

Навчальна карта