Глибока рекурсія
При глибокій рекурсії (тобто коли функція викликає саму себе багато разів, перш ніж дійти до базового випадку) у JavaScript може статися переповнення стека викликів - помилка RangeError: Maximum call stack size exceeded.
Що відбувається "під капотом"
Щоразу, коли функція викликає саму себе, JS створює новий контекст виконання (stack frame) у стеку викликів:
factorial(5)
→ factorial(4)
→ factorial(3)
→ factorial(2)
→ factorial(1)Кожен виклик зберігає:
- локальні змінні,
- аргументи,
- адресу повернення.
Коли базовий випадок досягнуто, стек "розмотується" назад. Але якщо викликів занадто багато - стек переповнюється.
Приклад переповнення стека
function recurse(n) {
console.log(n);
recurse(n + 1); // без базового випадку!
}
recurse(1);Помилка:
RangeError: Maximum call stack size exceededБраузер (або Node.js) виділяє обмежений розмір стека - зазвичай близько 10 000-20 000 вкладених викликів.
Навіть з базовим випадком можна "впертися" в ліміт
function countdown(n) {
if (n === 0) return;
countdown(n - 1);
}
countdown(100000); // RangeErrorПопри наявність базового випадку, глибина рекурсії (100 000) занадто велика для стека JS.
Як уникнути проблеми
1. Переписати рекурсію на цикл
function countdown(n) {
while (n > 0) n--;
}2. Використати хвостову рекурсію (якби була оптимізація)
function countdown(n) {
if (n === 0) return;
return countdown(n - 1); // хвостовий виклик
}Але: у більшості рушіїв JS tail call optimization не реалізована.
3. Розбити рекурсію на "порції" через setTimeout
function countdown(n) {
if (n === 0) return;
console.log(n);
setTimeout(() => countdown(n - 1), 0); // не блокує стек
}Тут кожен виклик виконується в новому циклі подій, тому стек не росте.
Підсумок
| Явище | Що відбувається |
|---|---|
| Глибока рекурсія | Багато вкладених викликів однієї функції |
| Результат | Переповнення стека (RangeError) |
| Чому | Кожен виклик створює новий контекст у стеку |
| Як уникнути | Використати цикл, хвостову рекурсію або setTimeout |
Коротка відповідь
Для співбесідиКоротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.