Що таке рекурсивний випадок?

АлгоритмиJunior~3 хв читання

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

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

Докладно

У будь-якій коректній рекурсивній функції є два ключові компоненти: базовий випадок (умова зупинки) і рекурсивний випадок (крок, який розбиває задачу і викликає функцію знову). Рекурсивний випадок повинен зменшувати складність задачі і приводити до одного або кількох подальших викликів, після чого результати цих викликів об'єднуються.

Структура рекурсивної функції

Базовий випадок: умова, за якої функція більше не викликає себе і одразу повертає відповідь (наприклад, порожня колекція, n = 0/1, вихід за межі).
Рекурсивний випадок: гілка, де функція викликає сама себе зі спрощеною підзадачею. Важливо: вона робить перевірюваний прогрес до базового випадку і, як правило, об'єднує отриманий підрезультат із поточним контекстом.
Крок прогресу: чітке зменшення задачі - n → n - 1, діапазон [l, r] → одна половина, вузол дерева → його діти, список → «голова» + «хвіст».
Комбінація результатів: як із часткових відповідей отримати підсумок (наприклад, n * factorial(n - 1), sum(left) + sum(right), concat(flatten(child))).
Практичний момент (JS): оптимізація хвостової рекурсії в більшості середовищ не гарантована, тому глибоко рекурсивні задачі краще переписувати ітеративно або обмежувати глибину.

Приклади реалізації

Факторіал (JavaScript)

function factorial(n) {
  if (n < 0) throw new Error('n must be non-negative');
  // Базовий випадок: 0! = 1, 1! = 1
  if (n === 0 || n === 1) return 1;
  // Рекурсивний випадок: n! = n * (n - 1)!
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

Тут рекурсивний випадок зменшує n на 1 і просувається до базового випадку n = 1 або 0, після чого результати перемножуються.

Обхід дерева (DFS)

const tree = {
  value: 1,
  children: [
    { value: 2, children: [] },
    { value: 3, children: [{ value: 4, children: [] }] }
  ]
};

function dfs(node, visit) {
  // Базовий випадок: порожній вузол
  if (!node) return;
  visit(node);
  // Рекурсивний випадок: обійти кожну дитину
  for (const child of node.children || []) {
    dfs(child, visit);
  }
}

dfs(tree, n => console.log(n.value)); // 1 2 3 4

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

Сума вкладеного масиву

function sumNested(arr) {
  let sum = 0;
  for (const item of arr) {
    if (Array.isArray(item)) {
      // Рекурсивний випадок: підсумувати підмасив
      sum += sumNested(item);
    } else {
      // Базовий випадок: примітивне число
      sum += item;
    }
  }
  return sum;
}

console.log(sumNested([1, [2, [3, 4]], 5])); // 15

Рекурсивний випадок обробляє вкладений масив, поки не дійде до чисел (базовий випадок).

Бінарний пошук (розділяй і володарюй)

function binarySearch(arr, target, left = 0, right = arr.length - 1) {
  // Базовий випадок: діапазон порожній
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid; // Базовий випадок: знайдено
  // Рекурсивний випадок: звузити пошук в одну з половин
  if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1);
  return binarySearch(arr, target, mid + 1, right);
}

console.log(binarySearch([1, 2, 3, 4, 5], 4)); // 3

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

Часті помилки в рекурсивному випадку

Немає базового випадку, або він недосяжний - нескінченна рекурсія і переповнення стека.
Немає прогресу - аргументи рекурсивного виклику не наближають до зупинки (наприклад, ви передаєте ті самі значення).
Експоненційне дублювання підзадач - класичний fib(n) без мемоізації (два рекурсивних виклики, великі перекриття). Рішення: мемоізація/динамічне програмування або ітерація.
Забули повернути результат рекурсивного виклику - функція завжди повертає undefined/невірний результат.
Мутація спільної структури між гілками - важко відстежувані баги. Краще робити чисті функції або копії, якщо потрібно.

Як перевірити коректність рекурсивного випадку

Ясно сформулюйте базовий випадок і покажіть, що він досяжний.
Доведіть прогрес: на кожному кроці вхід стає "меншим" (розмір, глибина, відстань, діапазон).
Визначте інваріант - що залишається істинним до і після рекурсивного кроку.
Перевірте комбінування результатів: чи коректно ви збираєте підсумок із підрезультатів.
Оцініть складність (часову і просторову) і уникайте надлишкових викликів (використовуйте мемоізацію, якщо потрібно).
Покрийте граничні випадки тестами: порожні входи, мінімальні/максимальні значення, глибока вкладеність.

Шаблон для співбесіди

function solve(problem) {
  // 1) Базовий випадок(и)
  if (isBase(problem)) return baseAnswer(problem);

  // 2) Прогрес: спростити задачу
  const smaller = reduce(problem);

  // 3) Рекурсивний випадок: розв'язати підзадачу
  const partial = solve(smaller);

  // 4) Комбінація результатів
  return combine(problem, partial);
}

Коли використовувати рекурсію

Дерева і графи: обходи (DFS), обчислення на піддеревах, пошук шляхів (з урахуванням множини відвіданих).
Розділяй і володарюй: бінарний пошук, швидке сортування, злиття, побудова сегментних дерев.
Бектрекінг: перебір з відкатами (генерація перестановок, N-ферзів, парсинг).
Задачі з природною рекурсивною структурою даних або формулою (наприклад, рекурсивні визначення).

Хвостова рекурсія та ітерація

Хвостова рекурсія - коли рекурсивний виклик є останньою операцією функції і результат повертається напряму. Це дозволяє потенційно оптимізувати стек, але в JavaScript така оптимізація не гарантована. Для великих глибин переважна ітерація або явний стек.

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

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

Premium

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