Які задачі розв'язує рекурсія

JavaScriptJunior~2 хв читання

Рекурсію часто застосовують для задач, де велику задачу можна природно розділити на підзадачі того самого типу. Нижче найтиповіші класи таких задач із прикладами на JavaScript.

Теорія

TL;DR

Математичні обчислення: факторіал, числа Фібоначчі, піднесення до степеня.
Обхід структур даних: дерева (DOM, файлова система), графи, DFS.
Робота з масивами: сума, пошук, фільтрація через «голова плюс хвіст».
Алгоритми «розділяй і володарюй»: QuickSort, MergeSort, бінарний пошук, Ханойська вежа.
Обробка вкладених структур: flatten масиву, обхід довільно вкладених об'єктів.
Логічні та комбінаторні задачі: перестановки, шлях у лабіринті, рюкзак.

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

javascript

// Піднесення до степеня через поділ задачі
function pow(x, n) {
  if (n === 0) return 1;      // базовий випадок
  return x * pow(x, n - 1);   // рекурсивний крок
}

console.log(pow(2, 10)); // 1024

Математичні обчислення

Класика, бо формула вже задана рекурентно.

Факторіал числа: n! = n * (n-1)!
Числа Фібоначчі: F(n) = F(n-1) + F(n-2)
Піднесення до степеня через поділ задачі:

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

Рекурсивний код тут майже дослівно повторює математичний запис, тому його легко перевірити очима.

Обхід структур даних

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

Дерева (наприклад, DOM, файлова система):

javascript
function traverse(node) { console.log(node.value); node.children.forEach(traverse); }
Графи: пошук у глибину (DFS) записується рекурсивно майже без зусиль; пошук у ширину (BFS) зазвичай реалізують через чергу, бо він іде рівнями, а не вглиб.

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

Масиви та вкладені структури

Масив зручно розглядати як «перший елемент плюс решта масиву».

Сума елементів, пошук, фільтрація:

javascript
function sum(arr) { if (arr.length === 0) return 0; return arr[0] + sum(arr.slice(1)); }
Розгортання (flatten) масиву:

javascript
function flatten(arr) { return arr.reduce((acc, val) => acc.concat(Array.isArray(val) ? flatten(val) : val), []); }

Саме вкладені структури, де глибина наперед невідома, є найсильнішим аргументом на користь рекурсії: циклом довелося б вести власний стек.

Алгоритми «розділяй і володарюй»

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

Швидке сортування (QuickSort)
Сортування злиттям (MergeSort)
Бінарний пошук
Алгоритм Ханойської вежі

javascript

function binarySearch(arr, target, lo = 0, hi = arr.length - 1) {
  if (lo > hi) return -1;                 // базовий випадок: нічого не лишилося
  const mid = (lo + hi) >> 1;
  if (arr[mid] === target) return mid;
  return arr[mid] < target
    ? binarySearch(arr, target, mid + 1, hi)
    : binarySearch(arr, target, lo, mid - 1);
}

Логічні та комбінаторні задачі

Перебір усіх комбінацій і перестановок;
пошук шляху в лабіринті;
розв'язання «зважених» задач типу рюкзака (knapsack).

javascript

function permutations(items) {
  if (items.length <= 1) return [items];          // базовий випадок
  return items.flatMap((item, i) => {
    const rest = [...items.slice(0, i), ...items.slice(i + 1)];
    return permutations(rest).map((p) => [item, ...p]);
  });
}

console.log(permutations(['a', 'b', 'c']).length); // 6

Тут рекурсія природно описує перебір з поверненням (backtracking): зробили вибір, пішли глибше, повернулися і спробували наступний.

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

Рекурсія там, де достатньо циклу. Лінійний прохід масивом циклом простіший і не має обмеження глибини стека.
arr.slice(1) на великому масиві. Кожен виклик копіює хвіст, тож замість O(n) виходить O(n^2) за часом і пам'яттю; краще передавати індекс.
Наївний fib без мемоізації. fib(n - 1) + fib(n - 2) дає експоненційну кількість викликів; кеш або цикл роблять його лінійним.
Обхід графа без множини відвіданих вузлів. Цикл у даних перетворює обхід на нескінченний.
Глибока рекурсія по великих даних. Обхід мільйона елементів впаде з RangeError: Maximum call stack size exceeded, навіть коли логіка правильна.
Забутий базовий випадок у комбінаторних задачах. Найчастіше це items.length <= 1 або порожня гілка дерева.

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

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

Premium

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