Трамплин (Trampoline)

Трамплин — техника выполнения рекурсии через итеративный цикл: функция возвращает не результат, а следующую функцию-шаг, а цикл вызывает их поочерёдно, избегая переполнения стека.

Зачем нужно

JavaScript не поддерживает оптимизацию хвостовых вызовов (TCO) в большинстве движков (V8 не поддерживает). Глубокая рекурсия приводит к RangeError: Maximum call stack size exceeded. Трамплин позволяет писать рекурсию в функциональном стиле и выполнять её итеративно без этого ограничения.

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

  • Обход глубоких деревьев и графов в функциональном стиле
  • Функциональные интерпретаторы и компиляторы
  • Бесконечные последовательности (ленивые вычисления)
  • Замена while с сохранением выразительности рекурсии

Проблема: переполнение стека

// Наивная рекурсия — падает при n > ~10000
function sumTo(n, acc = 0) {
  if (n === 0) return acc;
  return sumTo(n - 1, acc + n); // каждый вызов занимает кадр стека
}

sumTo(100000); // RangeError: Maximum call stack size exceeded

Трамплин: реализация

// Вместо результата возвращаем функцию-продолжение (thunk)
function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);
    // Пока результат — функция, вызываем её
    while (typeof result === 'function') {
      result = result;
    }
    return result;
  };
}

// Рекурсивная функция, возвращающая thunk вместо рекурсивного вызова
function sumToThunk(n, acc = 0) {
  if (n === 0) return acc;
  return  => sumToThunk(n - 1, acc + n); // возвращаем функцию!
}

const sumTo = trampoline(sumToThunk);
console.log(sumTo(100000)); // 5000050000 — без переполнения стека!

Как это работает (пошагово)

// sumTo(3) выполняется так:
// 1. sumToThunk(3, 0) →  => sumToThunk(2, 3)
// 2.  => sumToThunk(2, 3) →  => sumToThunk(1, 5)
// 3.  => sumToThunk(1, 5) →  => sumToThunk(0, 6)
// 4.  => sumToThunk(0, 6) → 6 (не функция — конец!)
// Стек никогда не растёт глубже 1 уровня

Практический пример: обход дерева

function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);
    while (typeof result === 'function') result = result;
    return result;
  };
}

// Подсчёт узлов дерева
function countNodes(node, acc = 0) {
  if (!node) return acc;
  if (!node.left && !node.right) return acc + 1;

  // Возвращаем thunk для следующего шага
  return  => countNodes(node.left, countNodes(node.right, acc + 1));
}

const count = trampoline(countNodes);
const tree = { val: 1, left: { val: 2, left: null, right: null }, right: { val: 3, left: null, right: null } };
console.log(count(tree)); // 3

Сравнение с итеративным подходом

// Итеративный — максимальная производительность
function sumToIterative(n) {
  let acc = 0;
  while (n > 0) { acc += n--; }
  return acc;
}

// Трамплин — функциональный стиль, не хуже по сложности O(n)
const sumTo = trampoline(sumToThunk);

// Трамплин выбирают, когда логика естественно рекурсивна,
// но глубина неограничена

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

// Альтернативный подход: используем объект-маркер
const bounce = (fn, ...args) => ({ isBounce: true, fn, args });
const done   = (value)       => ({ isBounce: false, value });

function trampoline2(fn) {
  return function(...args) {
    let result = fn(...args);
    while (result.isBounce) {
      result = result.fn(...result.args);
    }
    return result.value;
  };
}

const factorial = trampoline2(function fact(n, acc = 1) {
  if (n <= 1) return done(acc);
  return bounce(fact, n - 1, n * acc);
});

console.log(factorial(10)); // 3628800

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

1. Функция-шаг не возвращает thunk

function badStep(n, acc) {
  if (n === 0) return acc;
  badStep(n - 1, acc + n); // забыт return — возвращает undefined, не функцию!
  // Трамплин решит, что это результат
}

2. Трамплин без хвостовой рекурсии — не помогает

// Это НЕ хвостовой вызов — рекурсия не последнее действие
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // два рекурсивных вызова — трамплин не поможет напрямую
}

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

Ресурсы