Рекурсія в JavaScript
Що таке рекурсія
Рекурсією називають процес, коли функція викликає сама себе. Тобто, оголошується функцію і в її тілі відбувається звернення до неї (вона викликається). Важливою в рекурсії є гранична умова, при виконанні якої функція припинить викликатись і поверне якесь значення. Без цієї умови виникне помилка про переповнення стека викликів:
Uncaught RangeError: Maximum call stack size exceeded
На співбесідах дуже люблять ставити питання про рекурсію або запропонувати вирішити завдання використовуючи її, оскільки це один із базових принципів у програмуванні. Якщо ви Junior Front-End розробник, то дуже висока ймовірність, що на співбесіді спитають щось на цю тему, тому корисно знати, що таке рекурсія.
Приклад рекурсії
Класичний приклад рекурсії — це, звичайно, факторіал, його наводять у всіх книжках з програмування, де згадується рекурсія.
Про всяк випадок згадаємо, що це таке. У математиці факторіал числа n дорівнює добутку всіх позитивних чисел менших або рівних йому, і позначається як n! Формулою можна виразити так:
n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1
Наприклад, факторіал числа 4! = 1 * 2 * 3 * 4 = 24
, а для 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720
. Факторіал нуля дорівнює одиниці: 0! = 1
.
Щоб можна було порівняти різні підходи, для початку давайте наведемо приклад обчислення факторіалу JavaScript за допомогою простого циклу.
function factorial(n) {
let result = 1;
for (let i = n; i > 0; i--) {
result *= i;
}
return result;
}
Все досить просто, ініціалізуємо змінну та в циклі все перемножуємо. Але, можна ще простіше та коротше. Цикл йде у зворотному порядку, щоб наблизити його сенс до наступного прикладу.
Давайте тепер розв’яжемо завдання за допомогою рекурсії. Математично рекурсію можна виразити такою формулою:
n! = n * (n - 1)!
або
n! = n * (n - 1) * (n - 2)!
або
n! = n * (n - 1) * (n - 2) * (n - 3)!
І так далі, поки не дійдемо до нуля.
Тепер теж саме, але за допомогою JavaScript.
function factorial(n) {
if (n === 0) {
return 1;
}
return n * factorial(n - 1);
}
Як бачите цей приклад ще коротший і виглядає простіше. Спочатку описана гранична умова, коли n дорівнює нулю і який результат при цьому має бути. Нагадаю, що без цієї умови виникне помилка.
Рекурсивний виклик цієї функції для конкретного прикладу можна зобразити так:
factorial(4) = 4 * factorial(3);
factorial(4) = 4 * (3 * factorial(2));
factorial(4) = 4 * (3 * (2 * factorial(1)));
factorial(4) = 4 * (3 * (2 * (1 * factorial(0))));
factorial(4) = 4 * (3 * (2 * (1 * 1))));
factorial(0) = 1
, тому що ми маємо граничну умову, при n = 0
ми повертаємо 1
.
На цьому, про рекурсію в JavaScript, все. Сподіваюся, зміг допомогти веб-розробнику-початківцю зрозуміти, що таке рекурсія.