24 квітня 2022 р.

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

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

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

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

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

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

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

Щоб почати з чогось простого – давайте напишемо функцію 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

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

Рекурсія зазвичай коротша

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

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

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

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

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

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

  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-тегів (що, у свою чергу, можуть містити частини тексту/коментарі або інші теги тощо).

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

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

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

Imagine, we want to store an ordered list of objects.

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

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.

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

Завдання

важливість: 5

Напишіть функцію 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 варіанти рішення:

  1. Використання циклу.
  2. Використання рекурсії, у випадку sumTo(n) = n + sumTo(n-1) для n > 1.
  3. Використання формули [арифметичної прогресії] (https://uk.wikipedia.org/wiki/Арифметична_прогресія).

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

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): якщо рекурсивний виклик є останнім в функції (як у випадку з sumTo), то зовнішня функція не повинна відновлювати виконання, отже рушію не потрібно запам’ятовувати контекст виконання. Це зменшує використання пам’яті, тому підрахунок sumTo(100000) стає можливим. Але якщо рушій JavaScript не підтримує оптимізацію хвостового виклику (більшість з них не підтримує), то виникне помилка: максимальний розмір стека перевищиться, оскільки зазвичай є обмеження на загальний розмір стека.

важливість: 4

Факторіал з натурального числа – це число, помножене на "число мінус один", потім на "число мінус два" і так до 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
важливість: 5

The sequence of Fibonacci numbers has the formula Fn = Fn-1 + Fn-2. In other words, the next number is a sum of the two preceding ones.

First two numbers are 1, then 2(1+1), then 3(1+2), 5(2+3) and so on: 1, 1, 2, 3, 5, 8, 13, 21....

Fibonacci numbers are related to the Golden ratio and many natural phenomena around us.

Write a function fib(n) that returns the n-th Fibonacci number.

An example of work:

function fib(n) { /* your code */ }

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

P.S. The function should be fast. The call to fib(77) should take no more than a fraction of a second.

The first solution we could try here is the recursive one.

Fibonacci numbers are recursive by definition:

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

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // will be extremely slow!

…But for big values of n it’s very slow. For instance, fib(77) may hang up the engine for some time eating all CPU resources.

That’s because the function makes too many subcalls. The same values are re-evaluated again and again.

For instance, let’s see a piece of calculations for fib(5):

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

Here we can see that the value of fib(3) is needed for both fib(5) and fib(4). So fib(3) will be called and evaluated two times completely independently.

Here’s the full recursion tree:

We can clearly notice that fib(3) is evaluated two times and fib(2) is evaluated three times. The total amount of computations grows much faster than n, making it enormous even for n=77.

We can optimize that by remembering already-evaluated values: if a value of say fib(3) is calculated once, then we can just reuse it in future computations.

Another variant would be to give up recursion and use a totally different loop-based algorithm.

Instead of going from n down to lower values, we can make a loop that starts from 1 and 2, then gets fib(3) as their sum, then fib(4) as the sum of two previous values, then fib(5) and goes up and up, till it gets to the needed value. On each step we only need to remember two previous values.

Here are the steps of the new algorithm in details.

The start:

// a = fib(1), b = fib(2), these values are by definition 1
let a = 1, b = 1;

// get c = fib(3) as their sum
let c = a + b;

/* we now have fib(1), fib(2), fib(3)
a  b  c
1, 1, 2
*/

Now we want to get fib(4) = fib(2) + fib(3).

Let’s shift the variables: a,b will get fib(2),fib(3), and c will get their sum:

a = b; // now a = fib(2)
b = c; // now b = fib(3)
c = a + b; // c = fib(4)

/* now we have the sequence:
   a  b  c
1, 1, 2, 3
*/

The next step gives another sequence number:

a = b; // now a = fib(3)
b = c; // now b = fib(4)
c = a + b; // c = fib(5)

/* now the sequence is (one more number):
      a  b  c
1, 1, 2, 3, 5
*/

…And so on until we get the needed value. That’s much faster than recursion and involves no duplicate computations.

The full code:

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

The loop starts with i=3, because the first and the second sequence values are hard-coded into variables a=1, b=1.

The approach is called dynamic programming bottom-up.

важливість: 5

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

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);

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

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

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

важливість: 5

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

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

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

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

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

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);

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

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

Коментарі

прочитайте це, перш ніж коментувати…
  • Якщо у вас є пропозиції, щодо покращення підручника, будь ласка, створіть обговорення на GitHub або одразу створіть запит на злиття зі змінами.
  • Якщо ви не можете зрозуміти щось у статті, спробуйте покращити її, будь ласка.
  • Щоб вставити код, використовуйте тег <code>, для кількох рядків – обгорніть їх тегом <pre>, для понад 10 рядків – використовуйте пісочницю (plnkr, jsbin, codepen…)