Хвостовая рекурсия

Хвостовая рекурсия (Tail Call Recursion) — вид рекурсии, при котором рекурсивный вызов является последней операцией функции, что позволяет оптимизировать стек вызовов (TCO); в JavaScript эта оптимизация есть только в строгом режиме Safari, V8 (Node.js) её не реализует.

Зачем нужно

Обычная рекурсия создаёт новый кадр стека при каждом вызове. При глубокой рекурсии (10 000+ уровней) это приводит к RangeError: Maximum call stack size exceeded. Хвостовая рекурсия теоретически позволяет движку повторно использовать тот же кадр, не накапливая стек. На практике в JS это обходится через Трамплин (Trampoline) или итеративный рефакторинг.

Где используется

  • Алгоритмы на функциональных языках (Haskell, Elixir, Scala)
  • Понимание того, почему обычная рекурсия в JS ограничена
  • Как концепция при собеседованиях
  • Как промежуточный шаг перед трамплином

Обычная рекурсия (не хвостовая)

// Рекурсивный вызов — не последняя операция (нужно умножить на n)
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1); // вычисление после рекурсии → нельзя оптимизировать
}

// Стек вызовов для factorial(5):
// factorial(5) → ждёт factorial(4) → ждёт factorial(3) → ...
// 5 кадров стека открыты одновременно

Хвостовая рекурсия (tail-call)

Рекурсивный вызов — последнее действие; результат передаётся как аргумент:

// Хвостовая рекурсия: накапливаем результат в аккумуляторе
function factorialTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factorialTail(n - 1, n * acc); // рекурсия — последняя операция
  // Движок с TCO может заменить текущий кадр вместо добавления нового
}

factorialTail(5);     // 120
factorialTail(5, 1);  // то же самое явно

// Стек (при TCO):
// factorialTail(5, 1) → factorialTail(4, 5) → factorialTail(3, 20) → ...
// Только ОДИН кадр в памяти в каждый момент

Сумма через хвостовую рекурсию

// Не хвостовая (ждёт return нижнего уровня)
function sumTo(n) {
  if (n === 0) return 0;
  return n + sumTo(n - 1); // + после рекурсии
}

// Хвостовая (аккумулятор)
function sumToTail(n, acc = 0) {
  if (n === 0) return acc;
  return sumToTail(n - 1, acc + n); // результат в acc
}

Преобразование к хвостовой форме

Общий приём: ввести аккумулятор-параметр, в котором накапливается результат:

// Нехвостовая — вычисление после рекурсии
function reverse(arr) {
  if (arr.length === 0) return ;
  return [...reverse(arr.slice(1)), arr[0]]; // конкатенация после рекурсии
}

// Хвостовая с аккумулятором
function reverseTail(arr, acc = ) {
  if (arr.length === 0) return acc;
  return reverseTail(arr.slice(1), [arr[0], ...acc]);
}

reverseTail([1, 2, 3, 4]); // [4, 3, 2, 1]

Ситуация в JavaScript (реальность)

'use strict';
// Только строгий режим + хвостовая позиция + Safari (WebKit) = TCO

// V8 (Chrome, Node.js) — НЕ поддерживает TCO
// Даже хвостовая рекурсия упадёт при больших n:
function loop(n) {
  'use strict';
  if (n === 0) return 'done';
  return loop(n - 1); // хвостовой вызов
}

loop(100000); // RangeError в V8 (Chrome/Node.js)
              // OK в Safari (JavaScriptCore)

Практическая альтернатива: трамплин

// Хвостовой стиль + трамплин = нет переполнения в любом движке
function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);
    while (typeof result === 'function') result = result;
    return result;
  };
}

function sumToThunk(n, acc = 0) {
  if (n === 0) return acc;
  return  => sumToThunk(n - 1, acc + n); // thunk вместо прямого вызова
}

const sumTo = trampoline(sumToThunk);
console.log(sumTo(1000000)); // работает без ошибки

Частые ошибки

1. Считать, что хвостовая рекурсия работает во всех браузерах

// Не полагайся на TCO в Node.js / Chrome — используй трамплин или цикл

2. Неправильная хвостовая позиция

// НЕ хвостовая — операция после рекурсии
return fn(n - 1) + 1; // сложение выполняется ПОСЛЕ рекурсивного вызова

// Хвостовая — рекурсия последнее
return fn(n - 1, acc + 1);

Связанные темы

Ресурсы