Базовий випадок у рекурсії
Коротко: Базовий випадок - це умова, при якій рекурсивна функція перестає викликати себе і повертає результат одразу. Він зупиняє рекурсію.
Розгорнуте пояснення
У рекурсії задача ділиться на дрібніші підзадачі того самого типу. Щоб рекурсивний процес не був нескінченним, потрібна точка зупинки - базовий випадок. Коли вхідні дані досягають цієї "межі простоти", функція не робить рекурсивний виклик, а повертає готове значення.
Ознаки хорошого базового випадку:
- Однозначність - легко визначити, що далі ділити задачу немає сенсу.
- Повнота - базовий випадок покриває реальні "крайові" входи.
- Досяжність - кожен рекурсивний крок наближає аргументи до базового випадку.
Приклади:
- Факторіал:
javascript
function factorial(n) {
if (n === 0) return 1; // базовий випадок
return n * factorial(n - 1); // рекурсивний крок
}- Обхід масиву:
javascript
function sum(arr, i = 0) {
if (i === arr.length) return 0; // базовий випадок: порожній хвіст
return arr[i] + sum(arr, i + 1);
}- Пошук у дереві:
javascript
function find(node, target) {
if (!node) return null; // базовий: порожня гілка
if (node.value === target) return node; // базовий: знайдено
return find(node.left, target) || find(node.right, target);
}Типові помилки:
- Немає базового випадку -> нескінченна рекурсія і переповнення стека.
- Базовий випадок є, але рекурсивний крок не скорочує задачу (не наближає до бази).
- Неповний базовий випадок (не враховано
0, порожній масив,nullтощо).
Поради:
- Спочатку сформулюй базовий випадок словами, потім кодуй.
- Перевір, що кожен рекурсивний виклик робить вхід "простішим".
- Для кількох "країв" (наприклад,
n < 0,n === 0,n === 1) - визнач кілька базових випадків.
Коротка відповідь
Для співбесідиPremium
Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.