Пошук уроків, статей та іншого контенту
Дізнайтеся, як функція може викликати саму себе та чому рекурсії обов'язково потрібен базовий випадок. Розгляньте принцип роботи рекурсивних алгоритмів і ризик переповнення стеку викликів.
Рекурсія — це спосіб організації алгоритму, за якого функція викликає сама себе для розв’язання меншої версії тієї самої задачі.
Рекурсивна функція зазвичай складається з двох частин:
Базовий випадок — умова, за якої функція припиняє викликати саму себе.
Рекурсивний випадок — виклик функції з аргументом, наближеним до базового випадку.
Без базового випадку функція викликатиме сама себе нескінченно, доки JavaScript не завершить виконання через переповнення стеку викликів.
JavaScript зберігає інформацію про активні виклики функцій у спеціальній структурі даних — стеку викликів.
Коли функція викликається, у стек додається новий запис із локальними змінними та параметрами цієї функції. Коли функція завершується, її запис забирається зі стеку.
Розглянемо просту функцію:
function greet() {
console.log("Привіт");
}
greet();Під час виконання:
JavaScript додає greet до стеку.
Виконує тіло функції.
Видаляє greet зі стеку після завершення.
У рекурсивній функції новий виклик додається до стеку до того, як завершиться попередній:
function countDown(number) {
if (number === 0) {
console.log("Старт!");
return;
}
console.log(number);
countDown(number - 1);
}
countDown(3);Послідовність викликів буде такою:
countDown(3)
countDown(2)
countDown(1)
countDown(0)Для countDown(0) виконується базовий випадок. Після цього виклики завершуються у зворотному порядку.
Результат:
3
2
1
Старт!Розглянемо функцію, яка обчислює факторіал числа.
Факторіал числа n — це добуток усіх цілих чисел від 1 до n:
5! = 5 × 4 × 3 × 2 × 1 = 120Математично:
n! = n × (n - 1)!
0! = 1У цьому визначенні:
0! = 1 — базовий випадок;
n × factorial(n - 1) — рекурсивний випадок.
function factorial(number) {
if (number === 0) {
return 1;
}
return number * factorial(number - 1);
}
console.log(factorial(5)); // 120Як працює factorial(5):
factorial(5)
5 × factorial(4)
5 × 4 × factorial(3)
5 × 4 × 3 × factorial(2)
5 × 4 × 3 × 2 × factorial(1)
5 × 4 × 3 × 2 × 1 × factorial(0)
5 × 4 × 3 × 2 × 1 × 1
120Спочатку виклики накопичуються у стеку, а після досягнення базового випадку повертаються значення.
Перед написанням рекурсивної функції варто відповісти на три запитання:
Який найпростіший випадок можна розв’язати без рекурсії?
Як зменшити задачу до меншої?
Чи гарантовано кожен виклик наближається до базового випадку?
Наприклад, для підрахунку суми чисел від 1 до n:
function sumTo(number) {
if (number === 0) {
return 0;
}
return number + sumTo(number - 1);
}
console.log(sumTo(5)); // 15Розклад для sumTo(5):
sumTo(5) = 5 + sumTo(4)
= 5 + 4 + sumTo(3)
= 5 + 4 + 3 + sumTo(2)
= 5 + 4 + 3 + 2 + sumTo(1)
= 5 + 4 + 3 + 2 + 1 + sumTo(0)
= 15Тут:
базовий випадок: number === 0;
зменшення задачі: number - 1;
результат поточного кроку: number + ....
Не кожна рекурсивна функція просто виконує дію. Часто вона повертає результат, який використовує попередній виклик.
Наприклад, пошук найбільшого спільного дільника за алгоритмом Евкліда:
function greatestCommonDivisor(first, second) {
if (second === 0) {
return first;
}
return greatestCommonDivisor(second, first % second);
}
console.log(greatestCommonDivisor(48, 18)); // 6Послідовність обчислень:
gcd(48, 18)
gcd(18, 12)
gcd(12, 6)
gcd(6, 0)
6Базовий випадок настає, коли друге число дорівнює 0.
Рекурсія особливо корисна для роботи зі структурами, які самі мають вкладену структуру. Наприклад, об’єкт може містити інші об’єкти.
Функція нижче підраховує суму всіх числових значень у вкладеному об’єкті:
function sumNumbers(value) {
if (typeof value === "number") {
return value;
}
if (typeof value !== "object" || value === null) {
return 0;
}
let total = 0;
for (const nestedValue of Object.values(value)) {
total += sumNumbers(nestedValue);
}
return total;
}
const data = {
first: 10,
nested: {
second: 20,
deeper: {
third: 30
}
},
text: "JavaScript"
};
console.log(sumNumbers(data)); // 60Функція працює так:
якщо отримала число — повертає його;
якщо отримала не об’єкт — повертає 0;
якщо отримала об’єкт — рекурсивно обробляє кожне його значення.
Цей підхід можна використовувати для обходу дерев, вкладених конфігурацій, абстрактних синтаксичних дерев та інших ієрархічних даних.
Багато рекурсивних алгоритмів можна реалізувати за допомогою циклу.
Наприклад, факторіал через цикл:
function factorialIterative(number) {
let result = 1;
for (let current = 2; current <= number; current += 1) {
result *= current;
}
return result;
}
console.log(factorialIterative(5)); // 120Рекурсивна версія:
function factorialRecursive(number) {
if (number === 0) {
return 1;
}
return number * factorialRecursive(number - 1);
}
console.log(factorialRecursive(5)); // 120Рекурсивний підхід може бути зрозумілішим, якщо задача природно описується через вкладені підзадачі. Ітеративний підхід часто використовує менше пам’яті, оскільки не створює багато викликів функції у стеку.
Рекурсія добре підходить для:
обходу дерев;
обробки вкладених об’єктів і масивів;
алгоритмів пошуку з поверненням назад;
задач, які природно визначені через меншу версію самих себе;
алгоритмів на графах, якщо додатково контролювати відвідані вершини.
Цикли часто кращі для:
простого повторення дій;
обробки великої кількості послідовних елементів;
задач, де рекурсивна структура не додає зрозумілості;
ситуацій, у яких глибина рекурсії може бути великою.
Якщо рекурсивна функція не має базового випадку або не наближається до нього, виклики продовжують додаватися до стеку.
function infiniteRecursion() {
infiniteRecursion();
}
infiniteRecursion();У середовищі JavaScript така програма завершиться помилкою на кшталт:
RangeError: Maximum call stack size exceededЦе означає, що стек викликів переповнився.
Переповнення також можливе, якщо базовий випадок є, але до нього неможливо дійти:
function countDown(number) {
if (number === 0) {
return;
}
countDown(number + 1);
}
countDown(1);У цій функції число збільшується:
1 → 2 → 3 → 4 → ...Тому умова number === 0 ніколи не виконується.
Правильний варіант:
function countDown(number) {
if (number <= 0) {
return;
}
console.log(number);
countDown(number - 1);
}
countDown(3);Наївна рекурсія може багато разів обчислювати одні й ті самі значення.
Наприклад, рекурсивне обчислення чисел Фібоначчі:
function fibonacci(number) {
if (number <= 1) {
return number;
}
return fibonacci(number - 1) + fibonacci(number - 2);
}
console.log(fibonacci(10)); // 55Для обчислення fibonacci(10) функція неодноразово викликає fibonacci(5), fibonacci(4) та інші однакові підзадачі.
Для збереження вже обчислених результатів можна використати мемоізацію:
function createFibonacci() {
const cache = new Map([
[0, 0],
[1, 1]
]);
function fibonacci(number) {
if (cache.has(number)) {
return cache.get(number);
}
const result = fibonacci(number - 1) + fibonacci(number - 2);
cache.set(number, result);
return result;
}
return fibonacci;
}
const fibonacci = createFibonacci();
console.log(fibonacci(50)); // 12586269025У цьому прикладі Map зберігає вже знайдені значення. Завдяки цьому кожне число обчислюється лише один раз.
function printNumber(number) {
console.log(number);
printNumber(number - 1);
}Функція ніколи не завершується. Потрібно додати умову завершення:
function printNumber(number) {
if (number < 0) {
return;
}
console.log(number);
printNumber(number - 1);
}function process(number) {
if (number === 10) {
return;
}
process(number - 1);
}
process(0);Значення віддаляється від 10, а не наближається до нього. Потрібно змінити умову або напрямок зміни аргументу.
returnfunction sumTo(number) {
if (number === 0) {
return 0;
}
number + sumTo(number - 1);
}
console.log(sumTo(5)); // undefinedРезультат рекурсивного виклику не повертається назовні. Правильний варіант:
function sumTo(number) {
if (number === 0) {
return 0;
}
return number + sumTo(number - 1);
}
console.log(sumTo(5)); // 15Навіть правильна рекурсивна функція може переповнити стек, якщо кількість вкладених викликів дуже велика:
function countDown(number) {
if (number === 0) {
return;
}
countDown(number - 1);
}
countDown(1_000_000);Для великих послідовностей краще використати цикл:
function countDownIterative(number) {
for (let current = number; current > 0; current -= 1) {
// Тут можна виконати потрібну дію
}
}
countDownIterative(1_000_000);Базовий випадок має бути простим і зрозумілим. Якщо умова завершення захована серед складних обчислень, підвищується ризик помилки.
Краще явно розділяти:
function power(base, exponent) {
if (exponent === 0) {
return 1;
}
return base * power(base, exponent - 1);
}Перед запуском рекурсивної функції перевірте:
Чи є базовий випадок?
Чи можна до нього дійти з допустимими аргументами?
Чи змінюється аргумент під час кожного виклику?
Чи наближає ця зміна аргумент до базового випадку?
Чи повертається результат рекурсивного виклику?
Чи не буде глибина рекурсії надто великою?
Чи не обчислюються однакові підзадачі багато разів?
Рекурсія — це виклик функцією самої себе.
Кожна коректна рекурсивна функція має базовий і рекурсивний випадки.
Базовий випадок зупиняє рекурсію.
Рекурсивний випадок повинен наближати аргументи до базового випадку.
Кожен активний виклик займає місце у стеку викликів.
Надто глибока або нескінченна рекурсія спричиняє RangeError: Maximum call stack size exceeded.
Рекурсія зручна для вкладених структур і задач, які природно розкладаються на менші підзадачі.
Для простих повторюваних операцій цикл часто є ефективнішим і безпечнішим.
Мемоізація допомагає уникати повторного обчислення однакових підзадач.