Що таке базовий випадок рекурсії?

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

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

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

Докладне пояснення

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

Умова зупинки: логічна перевірка, за якої функція не робить рекурсивний виклик.
Повернення простого результату: відповідь відома напряму (наприклад, порожня колекція, нуль, одиниця, null-вузол).
Досяжність: кожен рекурсивний крок повинен наближати вхід до базового випадку.
Покриття граничних значень: базовий випадок коректно обробляє мінімальні/порожні входи.
Можливі кілька базових випадків: наприклад, для чисел Фібоначчі n = 0 і n = 1.

Чому базовий випадок важливий

Гарантія завершення: без нього рекурсія може стати нескінченною і переповнити стек.
Коректність: забезпечує правильну відповідь на мінімальних підзадачах, на якій будується індуктивний доказ.
Продуктивність: занадто вузький або недосяжний базовий випадок веде до зайвої роботи.
Безпека: запобігає переповненню стека та помилкам часу виконання.

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

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

javascript

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

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

Базовий випадок: n === 0 або n === 1. Рекурсивний крок зменшує n і робить базу досяжною.

Сума елементів масиву (JS)

javascript

function sum(arr) {
  if (arr.length === 0) return 0; // базовий випадок
  const [head, ...tail] = arr;
  return head + sum(tail);        // рекурсивний крок
}

console.log(sum([1,2,3,4])); // 10

Базовий випадок: порожній масив дає 0. Кожен крок зменшує масив, наближаючи його до порожнього.

НСД (алгоритм Евкліда)

javascript

function gcd(a, b) {
  if (b === 0) return Math.abs(a); // базовий випадок
  return gcd(b, a % b);             // рекурсивний крок
}

console.log(gcd(48, 18)); // 6

Базовий випадок: коли другий аргумент 0, відповідь відома напряму.

Кілька базових випадків: числа Фібоначчі

javascript

function fib(n) {
  if (n < 0) throw new Error('n must be >= 0');
  if (n === 0) return 0; // базовий випадок 1
  if (n === 1) return 1; // базовий випадок 2
  return fib(n - 1) + fib(n - 2);
}

console.log(fib(6)); // 8

Тут два базових випадки: для n = 0 і n = 1. Без них рекурсія не завершиться. На практиці для ефективності використовують мемоізацію або ітерацію.

Поширені помилки

Відсутній базовий випадок, або він не перевіряється першим.
Недосяжний базовий випадок: параметр не змінюється в бік бази (наприклад, n збільшується).
Занадто вузький базовий випадок: обробляє не всі граничні значення (наприклад, тільки n === 0, але не n === 1).
Побічні ефекти до перевірки бази: логувати/змінювати стан до того, як переконалися, що рекурсія не потрібна.

Як спроектувати базовий випадок

Визначте мінімальний вхід задачі: порожня структура, нульовий розмір, нульова глибина.
Сформулюйте відповідь на цьому мінімальному вході без рекурсії.
Переконайтеся, що кожен рекурсивний крок зменшує «розмір» задачі і досягає бази.
Перевірте граничні випадки: порожні, нульові, одиничні елементи.
Протестуйте на малих даних, де легко простежити хід виконання.

Базовий випадок у структурах даних

У рекурсивних обходах структур базою зазвичай є «порожня» форма структури:

Списки/масиви: порожній список/масив, індекс вийшов за межі.
Дерева: null-вузол (відсутність дочірнього елемента).
Графи: вершина вже відвідана (щоб зупинити повторні обходи).
Діапазони (divide-and-conquer): діапазон порожній або одиничної довжини (наприклад, length < 2).

Обхід бінарного дерева (JS)

javascript

function inorder(node) {
  if (node == null) return; // базовий випадок: порожній вузол
  inorder(node.left);
  console.log(node.value);
  inorder(node.right);
}

Базовий випадок зупиняє заглиблення, коли досягнуто відсутній дочірній вузол.

Підсумки

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

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

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

Premium

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