Хвостова рекурсія
Коротко: Хвостова рекурсія (tail recursion) - це така форма рекурсії, коли рекурсивний виклик є останньою дією функції (тобто після нього нічого не виконується).
Детальне пояснення
У звичайній рекурсії після кожного рекурсивного виклику функція повинна зберегти свій контекст (значення змінних, точку повернення тощо), щоб потім виконати решту операцій. Через це при глибокій рекурсії накопичуються виклики в стеку, і може статися переповнення стека (stack overflow).
Хвостова рекурсія вирішує цю проблему: якщо рекурсивний виклик - остання операція функції, то контекст не потрібно зберігати - інтерпретатор може оптимізувати виклик і повторно використати той самий стековий кадр. Це називається tail call optimization (TCO).
Приклад звичайної рекурсії
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1); // після виклику є операція множення
}Тут рекурсивний виклик не хвостовий,
тому що після нього виконується множення (* n).
Приклад хвостової рекурсії
function factorial(n, acc = 1) {
if (n === 1) return acc;
return factorial(n - 1, n * acc); // виклик - остання дія
}Тут виклик factorial(n - 1, n * acc) перебуває в хвості функції,
після нього нічого не виконується - це і є tail recursion.
Переваги
Менші витрати пам'яті - стек не росте. Швидше при великих глибинах рекурсії. Код залишається читабельним і безпечним.
Важливо
- У теорії JavaScript підтримує хвостову оптимізацію (за стандартом ES6).
- На практиці - майже жоден рушій JS (включно з V8 у Chrome і Node.js) її не реалізує. Тому хвостова рекурсія в JS не економить стек, але принцип залишається корисним для розуміння.
В одній фразі:
Хвостова рекурсія - це рекурсія, у якій останньою дією функції є рекурсивний виклик, що дозволяє оптимізувати виконання і уникнути росту стека.
Коротка відповідь
Для співбесідиКоротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.