Вступ
Рекурсія - це потужна концепція в програмуванні, яка передбачає, що функція викликає саму себе.
Спершу її буває трохи складно осягнути, але коли ми зрозуміємо основи, вона стає цінним інструментом для розвʼязання складних задач.
У цьому посібнику ми розглянемо рекурсію в JavaScript на простих для розуміння прикладах.
Що таке рекурсія?
Рекурсія виникає тоді, коли функція викликає саму себе, прямо чи опосередковано.
Вона схожа на цикл, але передбачає розбиття задачі на менші, зручніші для розвʼязання підзадачі.
Приклад 1: Зворотний відлік
Почнімо з простого прикладу: функція зворотного відліку.
function countdown(num) {
// Base case
if (num <= 0) {
console.log('Blastoff!');
return;
}
// Recursive case
console.log(num);
countdown(num - 1);
}
// Call the function
countdown(5);
У цьому прикладі:
-
Базовий випадок: коли
num стає меншим або дорівнює 0, функція виводить "Blastoff!" і припиняє викликати саму себе.
-
Рекурсивний випадок: функція виводить поточне значення
num і викликає саму себе з num - 1.
Приклад 2: Факторіал
А тепер розглянемо класичний приклад рекурсії: обчислення факторіала числа.
function factorial(n) {
// Base case
if (n === 0 || n === 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
// Test the function
console.log(factorial(5)); // Output: 120
У цьому прикладі:
-
Базовий випадок: коли
n дорівнює 0 або 1, функція повертає 1.
-
Рекурсивний випадок: функція множить
n на факторіал n - 1.
Ключові поняття
Базовий випадок
Кожна рекурсивна функція повинна мати принаймні один базовий випадок, тобто умову, за якої вона припиняє викликати саму себе.
Без базового випадку рекурсія тривала б нескінченно й призвела б до переповнення стека.
Рекурсивний випадок
Рекурсивний випадок визначає, як функція викликає саму себе з меншою або простішою версією задачі.
Переваги й недоліки рекурсії
Переваги:
- Витончене рішення для деяких задач.
- Наслідує концепцію математичної індукції.
Недоліки:
- Може бути менш ефективною, ніж ітеративні рішення.
- За глибокої рекурсії може призвести до переповнення стека.
Висновок
Рекурсія - цінна техніка, яка може спростити складні задачі, розбиваючи їх на менші, зручніші для розвʼязання підзадачі.
Розуміння базових і рекурсивних випадків має вирішальне значення для написання ефективних рекурсивних рішень у JavaScript.
Дізнатися більше:
Вказівки
Ми керуємо піцерією і пропонуємо три види піци:
- Margherita: $7
- Caprese: $9
- Formaggio: $10
Якщо клієнти хочуть, вони можуть додати необмежену кількість додаткових опцій: або «ExtraSauce» за $1, або «ExtraToppings» за $2.
Наше завдання - написати код, який допомагає клієнтові зʼясувати, скільки коштуватиме замовлення.
Обчисліть ціну піци
Функція приймає назву піци першим аргументом і необмежену кількість додаткових опцій, а повертає ціну піци в доларах.
pizzaPrice('Margherita');
// => 7
pizzaPrice('Caprese', 'ExtraSauce', 'ExtraToppings');
// => 12
pizzaPrice(
'Caprese',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
);
// => 17
Обчисліть загальну ціну замовлення
Функція приймає масив PizzaOrder і повертає загальну ціну замовлення в доларах.
У кожного PizzaOrder є властивість pizza (назва піци) і властивість extras (масив додаткових опцій).
const margherita = new PizzaOrder('Margherita');
const caprese = new PizzaOrder('Caprese', 'ExtraToppings');
orderPrice([margherita, caprese]);
// => 18
Ми побачимо, що не можемо написати це через рекурсію, бо один тест із величезною кількістю замовлень спричинить помилку Maximum call stack size exceeded.
Не хвилюймося, це навмисно: спробуймо реалізувати цю функцію за допомогою імперативного циклу!
Варіантів багато, зокрема, але не лише, можна використати reduce або цикл for.
Коли інтерпретатор JavaScript виконує код JavaScript, він веде облік того, у які функції він увійшов (почав викликати), у структурі даних під назвою «стек».
Коли функція повертає значення (завершується), її прибирають зі стека.
Однак стек має обмежений розмір.
Найпоширеніша помилка - рекурсивна функція, яка ніколи не завершується.
Кожен виклик потрапляє на стек, але перш ніж він поверне значення, на стек потрапляє ще один виклик.
function kaboom() {
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
Трасування стека цієї помилки показує той самий рядок знову й знову, і це логічно, бо функція викликає саму себе.
Хоча в більшості випадків це не має реального практичного застосування, можна зʼясувати, якої висоти може сягнути стек.
let calls = 0;
function kaboom() {
calls +=1 ;
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
console.log(calls)
// => a number, generally higher than 10.000
Існує лише два робочі розвʼязки помилки стека викликів, спричиненої синхронною рекурсивною функцією:
- переконатися, що функції повертають значення до досягнення ліміту стека, зазвичай додавши або виправивши базовий випадок.
- переписати рекурсивну функцію як імперативний цикл: він виконуватиме тіло циклу, не входячи у функцію, а отже, не збільшуючи стек.
Навчальна вправа
