Пошук уроків, статей та іншого контенту
Порівняйте рекурсивний та ітеративний підходи до розв'язання задач. Дізнайтеся, коли рекурсія робить алгоритм природнішим, а коли звичайний цикл є простішим і ефективнішим рішенням.
Рекурсія — це спосіб розв’язання задачі, за якого функція викликає саму себе з меншим або простішим набором даних.
Рекурсивна функція повинна мати дві частини:
Базовий випадок — умова, за якої функція припиняє виклики.
Рекурсивний крок — виклик функції для спрощеної версії задачі.
function countdown(number) {
if (number === 0) {
return;
}
console.log(number);
countdown(number - 1);
}
countdown(3);
// 3
// 2
// 1У цьому прикладі:
number === 0 — базовий випадок;
countdown(number - 1) — рекурсивний крок.
Якщо забути базовий випадок або не наближатися до нього, функція викликатиме сама себе нескінченно.
Ітерація — це повторення дій за допомогою циклу for, while або іншого механізму повторення.
Ту саму задачу можна розв’язати без рекурсії:
function countdown(number) {
while (number > 0) {
console.log(number);
number -= 1;
}
}
countdown(3);
// 3
// 2
// 1Цикл явно зберігає поточний стан у змінній number. Рекурсивний варіант зберігає цей стан у стеку викликів функцій.
Факторіал невід’ємного числа n визначається так:
n! = n × (n - 1) × ... × 1
0! = 1function factorialRecursive(number) {
if (number < 0) {
throw new Error("Факторіал визначений лише для невід'ємних чисел");
}
if (number === 0) {
return 1;
}
return number * factorialRecursive(number - 1);
}
console.log(factorialRecursive(5)); // 120Виклик factorialRecursive(5) розгортається приблизно так:
5 * factorialRecursive(4)
5 * 4 * factorialRecursive(3)
5 * 4 * 3 * factorialRecursive(2)
5 * 4 * 3 * 2 * factorialRecursive(1)
5 * 4 * 3 * 2 * 1 * factorialRecursive(0)
5 * 4 * 3 * 2 * 1 * 1function factorialIterative(number) {
if (number < 0) {
throw new Error("Факторіал визначений лише для невід'ємних чисел");
}
let result = 1;
for (let current = 2; current <= number; current += 1) {
result *= current;
}
return result;
}
console.log(factorialIterative(5)); // 120Обидва рішення мають часову складність O(n). Однак ітеративний варіант зазвичай використовує менше пам’яті:
рекурсія: O(n) пам’яті для стеку викликів;
цикл: O(1) додаткової пам’яті.
Для факторіала цикл часто є практичнішим: його логіка проста, а рекурсія не додає суттєвої виразності.
Під час виклику функції JavaScript зберігає інформацію про нього у стеку викликів.
Розглянемо функцію:
function sumTo(number) {
if (number === 0) {
return 0;
}
return number + sumTo(number - 1);
}
console.log(sumTo(3)); // 6Поки sumTo(3) ще не повернула результат, у стеку зберігаються виклики:
sumTo(3)
sumTo(2)
sumTo(1)
sumTo(0)Коли досягається базовий випадок, виклики починають завершуватися у зворотному порядку.
Якщо рекурсія надто глибока, стек може переповнитися. У JavaScript це зазвичай призводить до помилки:
RangeError: Maximum call stack size exceededТочна максимальна глибина залежить від середовища виконання, тому не варто розраховувати на конкретне число викликів.
Наприклад, потрібно знайти суму елементів масиву.
function sumRecursive(numbers, index = 0) {
if (index === numbers.length) {
return 0;
}
return numbers[index] + sumRecursive(numbers, index + 1);
}
console.log(sumRecursive([2, 4, 6, 8])); // 20function sumIterative(numbers) {
let sum = 0;
for (const number of numbers) {
sum += number;
}
return sum;
}
console.log(sumIterative([2, 4, 6, 8])); // 20Ітеративний варіант тут зазвичай кращий:
він коротший;
не використовує стек рекурсивних викликів;
його простіше відлагоджувати;
він не ризикує впертися в обмеження глибини стеку.
Рекурсивний варіант може бути корисним як навчальна ілюстрація або частина іншого рекурсивного алгоритму.
Рекурсія особливо добре підходить для структур, які самі мають вкладену або ієрархічну будову.
Типові приклади:
дерева;
файлові каталоги;
вкладені об’єкти;
DOM-структури;
графи;
алгоритми «розділяй і володарюй»;
перебір усіх комбінацій і варіантів.
Уявімо дерево категорій:
const categories = {
name: "Товари",
children: [
{
name: "Електроніка",
children: [
{ name: "Телефони", children: [] },
{ name: "Ноутбуки", children: [] }
]
},
{
name: "Одяг",
children: [
{ name: "Футболки", children: [] }
]
}
]
};
function printTree(node, level = 0) {
const indentation = " ".repeat(level);
console.log(`${indentation}- ${node.name}`);
for (const child of node.children) {
printTree(child, level + 1);
}
}
printTree(categories);Результат:
- Товари
- Електроніка
- Телефони
- Ноутбуки
- Одяг
- ФутболкиРекурсивна функція тут відповідає структурі даних:
вивести поточний вузол;
для кожної дочірньої категорії виконати ті самі дії.
function findCategory(node, name) {
if (node.name === name) {
return node;
}
for (const child of node.children) {
const result = findCategory(child, name);
if (result !== null) {
return result;
}
}
return null;
}
const result = findCategory(categories, "Ноутбуки");
console.log(result);
// { name: "Ноутбуки", children: [] }Без рекурсії для такої задачі довелося б вручну керувати масивом вузлів для подальшої обробки. Це можливо, але часто менш наочно.
Потрібно розрізняти:
часову складність — скільки операцій виконується;
просторову складність — скільки додаткової пам’яті використовується.
Для простого обходу дерева:
function countNodes(node) {
let count = 1;
for (const child of node.children) {
count += countNodes(child);
}
return count;
}Якщо кожен вузол обробляється один раз:
часова складність — O(n), де n — кількість вузлів;
пам’ять для стеку — O(h), де h — максимальна глибина дерева.
Для збалансованого дерева h може бути близькою до log n, а для виродженого дерева — дорівнювати n.
Ітеративний варіант може зберігати вузли у власному стеку:
function countNodesIterative(root) {
let count = 0;
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
count += 1;
for (const child of node.children) {
stack.push(child);
}
}
return count;
}
console.log(countNodesIterative(categories)); // 6Обидва варіанти мають подібну асимптотику. Різниця в тому, хто керує стеком:
у рекурсивному варіанті — механізм викликів JavaScript;
в ітеративному — масив stack у коді програми.
Деякі рекурсивні алгоритми повторно обчислюють ті самі значення. Класичний приклад — числа Фібоначчі.
Наївний варіант має експоненційну складність:
function fibonacciRecursive(number) {
if (number <= 1) {
return number;
}
return fibonacciRecursive(number - 1)
+ fibonacciRecursive(number - 2);
}
console.log(fibonacciRecursive(10)); // 55Для великих значень ця функція повільна, бо багато разів обчислює однакові підзадачі.
Мемоізація зберігає вже знайдені результати:
function fibonacciMemoized(number, cache = new Map()) {
if (number <= 1) {
return number;
}
if (cache.has(number)) {
return cache.get(number);
}
const result = fibonacciMemoized(number - 1, cache)
+ fibonacciMemoized(number - 2, cache);
cache.set(number, result);
return result;
}
console.log(fibonacciMemoized(50)); // 12586269025Мемоізація зменшує часову складність до O(n), але використовує додаткову пам’ять для кешу та стеку викликів.
Для цієї конкретної задачі ще простіше використати цикл:
function fibonacciIterative(number) {
if (number <= 1) {
return number;
}
let previous = 0;
let current = 1;
for (let index = 2; index <= number; index += 1) {
const next = previous + current;
previous = current;
current = next;
}
return current;
}
console.log(fibonacciIterative(50)); // 12586269025Цикл використовує O(1) додаткової пам’яті та не залежить від глибини стеку.
Хвостова рекурсія — це рекурсивний виклик, результат якого одразу повертається без додаткових операцій.
function factorialTailRecursive(number, result = 1) {
if (number === 0) {
return result;
}
return factorialTailRecursive(number - 1, result * number);
}У деяких мовах компілятор може оптимізувати такі виклики й не створювати новий стековий кадр. У JavaScript не слід розраховувати на таку оптимізацію в поширених середовищах виконання.
Тому хвостова рекурсія не гарантує безпечної обробки дуже великих значень. Якщо глибина викликів може бути значною, краще використати цикл.
Поставте собі такі запитання.
Якщо дані природно утворюють дерево або вкладені рівні, рекурсія часто робить код зрозумілішим.
Приклад:
function calculateNestedSum(value) {
if (typeof value === "number") {
return value;
}
return value.reduce((sum, item) => {
return sum + calculateNestedSum(item);
}, 0);
}
console.log(calculateNestedSum([1, [2, [3, 4]], 5])); // 15Для підрахунку, накопичення результату або проходження масиву зазвичай достатньо циклу.
function findMaximum(numbers) {
if (numbers.length === 0) {
return undefined;
}
let maximum = numbers[0];
for (let index = 1; index < numbers.length; index += 1) {
if (numbers[index] > maximum) {
maximum = numbers[index];
}
}
return maximum;
}
console.log(findMaximum([4, 9, 2, 7])); // 9Якщо вхідні дані можуть спричинити тисячі або мільйони вкладених викликів, рекурсія небезпечна через обмежений стек.
У такому випадку використовуйте:
цикл;
власний стек на основі масиву;
алгоритм із меншою глибиною викликів.
Іноді рекурсивна версія значно краще передає ідею алгоритму. Якщо глибина контрольована, а продуктивність достатня, це може бути правильним вибором.
В інших випадках цикл:
швидше виконується;
використовує менше пам’яті;
легше контролюється;
краще працює на великих вхідних даних.
природно описує дерева та вкладені структури;
може зробити алгоритм коротшим і наочнішим;
добре підходить для обходу графів, backtracking та «розділяй і володарюй»;
зменшує кількість явних змінних для керування станом.
використовує стек викликів;
може завершитися помилкою переповнення стеку;
іноді має більші витрати пам’яті;
складніше відлагоджується при великій глибині;
легко отримати нескінченну рекурсію.
зазвичай ефективніші для лінійних задач;
використовують передбачувану кількість пам’яті;
не залежать від глибини стеку;
зручні для обробки великих масивів і числових послідовностей.
для вкладених структур можуть вимагати власного стеку або черги;
код обходу дерева може стати складнішим;
стан алгоритму іноді доводиться зберігати вручну.
function broken(number) {
return broken(number - 1);
}Функція ніколи не завершується коректно.
function broken(number) {
if (number === 0) {
return 0;
}
return broken(number + 1);
}Значення збільшується, хоча для базового випадку потрібно рухатися до 0.
Рекурсивна функція повинна визначати, що робити з порожнім масивом, null, листком дерева або іншим граничним значенням.
function sum(numbers) {
if (numbers.length === 0) {
return 0;
}
return numbers[0] + sum(numbers.slice(1));
}Цей приклад коректний логічно, але slice(1) створює новий масив на кожному кроці. Для великих масивів краще передавати індекс:
function sum(numbers, index = 0) {
if (index === numbers.length) {
return 0;
}
return numbers[index] + sum(numbers, index + 1);
}Операції на кшталт slice, concat або створення нових об’єктів у кожному рекурсивному виклику можуть суттєво погіршити продуктивність.
Передавайте індекси або використовуйте змінюваний стек, якщо це не суперечить вимогам до незмінності даних.
Якщо задачу легко описати одним циклом, рекурсивне рішення не обов’язково буде кращим. Не варто використовувати рекурсію лише тому, що вона виглядає коротшою.
Визначте, чи має задача вкладену структуру.
Знайдіть базовий випадок.
Переконайтеся, що кожен крок наближає до нього.
Оцініть максимальну глибину викликів.
Порівняйте часову та просторову складність.
Перевірте граничні випадки:
порожній масив;
нуль;
від’ємне число;
один елемент;
дуже великий вхід.
Якщо рекурсія не додає зрозумілості, розгляньте цикл.
Рекурсія — це виклик функцією самої себе.
Кожна рекурсивна функція повинна мати базовий випадок і крок, що наближає до нього.
Рекурсія використовує стек викликів і може спричинити переповнення стеку.
Цикли зазвичай ефективніші для простих послідовних операцій.
Рекурсія природна для дерев, графів, вкладених даних і задач із підзадачами.
Ітеративний алгоритм може замінити рекурсію за допомогою циклу та явного стеку.
Хвостова рекурсія в JavaScript не гарантує відсутності переповнення стеку.
Вибір підходу залежить від структури задачі, вимог до пам’яті, глибини викликів і зрозумілості коду.