Пошук уроків, статей та іншого контенту
Функції, що викликають самі себе: базовий і рекурсивний випадок, стек викликів та коли рекурсія доречна.
Рекурсивна функція — це функція, яка викликає саму себе для розв'язання меншої версії тієї самої задачі. Кожна рекурсивна функція має дві обов'язкові частини: базовий випадок (умова зупинки) і рекурсивний випадок (виклик самої себе з іншими аргументами, що наближають до базового випадку).
function factorial(n) {
if (n <= 1) return 1; // базовий випадок — зупиняє рекурсію
return n * factorial(n - 1); // рекурсивний випадок
}
factorial(5); // 5 * 4 * 3 * 2 * 1 = 120Забутий або недосяжний базовий випадок призводить до переповнення стека викликів (call stack):
function broken(n) {
return n * broken(n - 1); // немає умови зупинки
}
broken(5); // RangeError: Maximum call stack size exceededКожен рекурсивний виклик додає новий кадр (frame) у стек викликів. Стек має обмежений розмір — тисячі вкладених викликів без зупинки завершаться помилкою RangeError.
function sumArray(arr) {
if (arr.length === 0) return 0; // базовий випадок — порожній масив
const [first, ...rest] = arr;
return first + sumArray(rest); // рекурсивний випадок — менший масив
}
sumArray([1, 2, 3, 4]); // 10Там, де дані природно вкладені (файлова система, DOM, дерево коментарів), рекурсія читається набагато природніше за цикли:
function countFiles(node) {
if (node.type === "file") return 1;
return node.children.reduce((total, child) => total + countFiles(child), 0);
}Рекурсія читається природніше для задач із самоподібною, вкладеною структурою (дерева, вкладені об'єкти).
Цикл зазвичай ефективніший за пам'яттю — не створює новий кадр стека на кожен крок.
У JavaScript немає гарантованої оптимізації хвостової рекурсії (tail-call optimization) у більшості рушіїв, тому для дуже глибокої рекурсії (десятки тисяч рівнів) цикл — безпечніший вибір.
Відсутній або недосяжний базовий випадок — нескінченна рекурсія до переповнення стека.
Рекурсивний виклик з аргументом, який не наближається до базового випадку (наприклад, n + 1 замість n - 1).
Використання рекурсії для простих лінійних задач, де звичайний цикл читається так само добре, але ефективніший.
Рекурсія розв'язує задачу через виклик тієї самої функції з простішим варіантом вхідних даних, доки не буде досягнуто базового випадку. Найкорисніша для вкладених, деревоподібних структур даних — для простих лінійних задач цикл зазвичай ефективніший і не менш читабельний.
Спробуйте самостійно
Напишіть рекурсивну функцію fibonacci(n), яка повертає n-те число Фібоначчі (0, 1, 1, 2, 3, 5, 8...). Визначте базовий випадок самостійно.