Що таке рекурсія?

JavaScript~3 хв читання

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

Теорія

TL;DR

Уяви матрьошку: відкриваєш одну, всередині менша, і так далі, поки не дійдеш до найменшої, всередині якої вже нічого немає.
Кожна рекурсивна функція потребує двох речей: базового випадку (умова зупинки) і рекурсивного виклику (виклик себе з меншим аргументом).
Рекурсія добре підходить для дерев, графів і вкладених структур. Для плоских даних використовуй цикл, щоб не переповнити стек.
Node.js і браузери дозволяють приблизно 10,000 фреймів у стеку викликів, після чого кидають RangeError: Maximum call stack size exceeded.

Швидкий приклад

javascript

function factorial(n) {
  if (n <= 1) return 1;        // базовий випадок: зупинка
  return n * factorial(n - 1); // рекурсивний виклик: менша задача
}

console.log(factorial(5)); // 120
// Стек: factorial(5) -> 5 * factorial(4) -> ... -> 5 * 4 * 3 * 2 * 1

Кожен виклик додає фрейм до стека викликів. Коли factorial(1) повертає 1, стек розкручується назад, і кожен фрейм множить своє n на результат попереднього.

V8 (Chrome/Node.js) кладе кожен рекурсивний виклик у стек як новий контекст виконання зі своїми локальними змінними. Фрейми чекають там, поки не спрацює базовий випадок. Потім значення розкручуються назад через кожен фрейм у зворотному порядку.

Стандартна глибина стека в Node.js становить близько 10,000 фреймів. Перевищиш і отримаєш RangeError: Maximum call stack size exceeded. Саме тому factorial(100000) завалить Node.js, і саме тому рекурсія для великих плоских масивів є поганим вибором.

Коли використовувати

Обхід дерева або графу (DOM, файлова система, дерево компонентів): структура вкладена, тому рекурсія відображає її напряму.
Парсинг вкладених даних (JSON, HTML): кожен вузол може мати дочірні вузли тієї ж форми.
Алгоритми "розділяй і пануй" (quicksort, merge sort): задача ділиться навпіл з кожним викликом.
Великі плоскі масиви: використовуй цикл. Немає вкладеності, немає переваги, є тільки ризик переповнення стека.
Fibonacci без оптимізації: підходить для демонстрацій, але складність O(2^n). Перед деплоєм додай мемоізацію.

Типові помилки

Немає базового випадку:

javascript

function bad(n) {
  return n * bad(n - 1); // немає умови зупинки
}
// RangeError: Maximum call stack size exceeded

Рішення: додати if (n <= 1) return 1; перед рекурсивним викликом.

Аргумент не зменшується:

javascript

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n); // n не змінюється, нескінченний цикл
}

Передати n замість n - 1 - одна з найпоширеніших помилок у код-рев'ю. Функція виглядає нормально на перший погляд. Node.js повідомить про проблему тільки коли стек вичерпається.

Рішення: передавати n - 1. Кожен виклик повинен наближати до базового випадку.

Ігнорування глибини стека: factorial(100000) завалить Node.js. Якщо вхідні дані можуть бути великими, використовуй ітеративний підхід. Можна збільшити стек через node --stack-size=65500, але це обхідне рішення, не виправлення.

Де зустрічається

React Fiber обходить дерево компонентів рекурсивно під час рендерингу (reconciler йде вглибину).
Lodash _.flattenDeep рекурсивно обходить вкладені масиви для повного вирівнювання.
Обхід директорій у Node.js використовує рекурсивні патерни для обходу файлової ієрархії.
D3.js рекурсивно обходить ієрархії вузлів для розрахунку позицій у деревовидних візуалізаціях.

Питання на співбесіді

Q: Напиши factorial ітеративно.
A: function factIter(n, acc = 1) { if (n <= 1) return acc; return factIter(n - 1, acc * n); }. Формально це хвостова рекурсія, але V8 її не оптимізує, тому стек все одно зростає.

Q: Яка часова складність наївної рекурсії для Fibonacci?
A: O(2^n). Кожен виклик розгалужується на два, тому загальна кількість викликів подвоюється на кожному рівні. Виправляється мемоізацією або ітеративним підходом знизу вгору.

Q: Чи підтримує JavaScript оптимізацію хвостових викликів (TCO)?
A: Ні. V8 не виконує TCO на практиці. Навіть правильно написаний хвостовий виклик все одно додає фрейм у стек. Для глибокої рекурсії використовуй цикл.

Q: Що відбувається з рекурсивним стеком, якщо користувач переключає вкладку браузера під час виконання?
A: JavaScript однопотоковий. Браузер призупиняє виконання, коли вкладка втрачає фокус, і відновлює при поверненні. Важка рекурсія, що блокує головний потік, заморожує UI до повного розкручування стека. Для затратних операцій використовуй setTimeout або Web Workers.

Приклади

Базовий: сума всіх чисел у масиві

javascript

function sumArray(arr, index = 0) {
  if (index >= arr.length) return 0;            // базовий випадок: вийшли за межі
  return arr[index] + sumArray(arr, index + 1); // додаємо поточний, рекурсія на решту
}

console.log(sumArray([1, 2, 3, 4])); // 10
// Розкручується як: 1 + (2 + (3 + (4 + 0)))

Базовий випадок спрацьовує, коли index досягає довжини масиву. Далі кожен фрейм повертає свій елемент плюс суму всього, що правіше.

Середній: рендер вкладеного дерева компонентів

Спрощена версія того, що React робить при обході дерева компонентів:

javascript

function renderTree(node) {
  if (!node.children || node.children.length === 0) {
    return `<div>${node.text}</div>`; // базовий випадок: листовий вузол
  }

  let html = `<div>${node.text}`;
  node.children.forEach(child => {
    html += renderTree(child); // рекурсія для кожного дочірнього вузла
  });
  return html + '</div>';
}

const tree = {
  text: 'App',
  children: [
    { text: 'Header', children: [] },
    { text: 'Main', children: [{ text: 'Article', children: [] }] }
  ]
};

console.log(renderTree(tree));
// <div>App<div>Header</div><div>Main<div>Article</div></div></div>

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

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

Дочитали статтю?