Что такое хвостовая рекурсия?

Хвостовая рекурсия (Tail Recursion)

Хвостовая рекурсия — это особый вид рекурсии, где рекурсивный вызов функции является последним операцией, выполняемой функцией. Это позволяет компилятору или интерпретатору оптимизировать код и избежать переполнения стека вызовов.

Что такое стек вызовов

Когда функция вызывает сама себя, каждый вызов добавляется в стек вызовов:

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);  // Рекурсивный вызов НЕ последний
}

factorial(5);
// Стек вызовов:
// factorial(5) * factorial(4)
// factorial(5) * (4 * factorial(3))
// factorial(5) * (4 * (3 * factorial(2)))
// factorial(5) * (4 * (3 * (2 * factorial(1))))
// factorial(5) * (4 * (3 * (2 * 1)))

Каждый вызов ждёт результата предыдущего — это требует памяти. При глубокой рекурсии может произойти Stack Overflow (переполнение стека).

Нехвостовая рекурсия (Non-tail recursion)

Рекурсивный вызов НЕ последний — требуется что-то сделать после возврата:

// Нехвостовая рекурсия
function sum(arr, index = 0) {
  if (index === arr.length) return 0;
  return arr[index] + sum(arr, index + 1);  // После возврата: сложение
}

sum([1, 2, 3, 4, 5]);
// sum(arr, 0) => 1 + sum(arr, 1)
//              => 1 + (2 + sum(arr, 2))
//              => 1 + (2 + (3 + sum(arr, 3)))
// Нужно хранить все промежуточные значения

Хвостовая рекурсия (Tail recursion)

Рекурсивный вызов — последняя операция:

// Хвостовая рекурсия
function sumTail(arr, index = 0, accumulator = 0) {
  if (index === arr.length) return accumulator;
  return sumTail(arr, index + 1, accumulator + arr[index]);
  // Рекурсивный вызов - последняя операция!
}

sumTail([1, 2, 3, 4, 5]);
// sumTail(arr, 0, 0)
// sumTail(arr, 1, 1)
// sumTail(arr, 2, 3)
// sumTail(arr, 3, 6)
// sumTail(arr, 4, 10)
// sumTail(arr, 5, 15) => 15

Здесь не нужно хранить промежуточные вычисления — компилятор может просто заменить переменные в памяти.

Примеры хвостовой рекурсии

1. Факториал

// Нехвостовая рекурсия
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);  // Умножение ПОСЛЕ вызова
}

// Хвостовая рекурсия
function factorialTail(n, accumulator = 1) {
  if (n <= 1) return accumulator;
  return factorialTail(n - 1, n * accumulator);  // Умножение ДО вызова
}

console.log(factorial(5));        // 120
console.log(factorialTail(5));    // 120

2. Поиск элемента в массиве

// Нехвостовая
function find(arr, target, index = 0) {
  if (index === arr.length) return -1;
  if (arr[index] === target) return index;
  return find(arr, target, index + 1);  // Возврат значения ДО вызова
}

// Хвостовая
function findTail(arr, target, index = 0) {
  if (index === arr.length) return -1;
  if (arr[index] === target) return index;  // Прямой возврат
  return findTail(arr, target, index + 1);  // Рекурсия - последняя операция
}

3. Обход дерева

class Node {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

// Нехвостовая рекурсия (обход в глубину)
function traverseNonTail(node, callback) {
  if (!node) return;
  callback(node.value);
  traverseNonTail(node.left, callback);   // Два рекурсивных вызова
  traverseNonTail(node.right, callback);  // Не хвостовая
}

// Хвостовая рекурсия (требует трансформации)
function traverseTail(node, callback, queue = []) {
  if (!node) {
    if (queue.length === 0) return;
    return traverseTail(queue.shift(), callback, queue);  // Хвостовая
  }
  
  callback(node.value);
  if (node.left) queue.push(node.left);
  if (node.right) queue.push(node.right);
  return traverseTail(queue.shift() || null, callback, queue);
}

Оптимизация компилятором: TCO (Tail Call Optimization)

TCO — когда компилятор преобразует хвостовую рекурсию в итерацию:

// Компилятор может преобразовать это:
function sumTail(arr, index = 0, accumulator = 0) {
  if (index === arr.length) return accumulator;
  return sumTail(arr, index + 1, accumulator + arr[index]);
}

// В эквивалент этому (псевдокод):
function sumOptimized(arr) {
  let index = 0;
  let accumulator = 0;
  
  while (index < arr.length) {
    accumulator += arr[index];
    index++;
  }
  
  return accumulator;
}

Важно: TCO поддерживается не всеми языками/средами:

• ES2015 (ES6) — в спецификации есть TCO
• Safari — поддерживает
• Node.js — использует V8, которая НЕ гарантирует TCO
• Chrome/Firefox — зависит от реализации

// В Node.js этот код может привести к переполнению стека:
function countDown(n) {
  if (n === 0) return;
  console.log(n);
  return countDown(n - 1);  // Хвостовая рекурсия, но TCO не гарантирована
}

countDown(1000000); // RangeError: Maximum call stack size exceeded

Практические рекомендации

1. Преобразуй в итерацию

Осторожнее всего — использовать цикл:

// Вместо рекурсии
function sumRecursive(arr, index = 0, acc = 0) {
  if (index === arr.length) return acc;
  return sumRecursive(arr, index + 1, acc + arr[index]);
}

// Используй цикл
function sumLoop(arr) {
  let sum = 0;
  for (const num of arr) {
    sum += num;
  }
  return sum;
}

// Или reduce
const sum = arr.reduce((acc, num) => acc + num, 0);

2. Используй аккумулятор (accumulator pattern)

Для хвостовой рекурсии передавай результаты как параметр:

function processRecursive(data, index = 0, result = []) {
  if (index === data.length) return result;
  result.push(data[index] * 2);
  return processRecursive(data, index + 1, result);
}

3. Трамполининг (для особых случаев)

Если нужна рекурсия, использование трамполина:

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

function factorialTramped(n, acc = 1) {
  if (n <= 1) return acc;
  return () => factorialTramped(n - 1, n * acc);
}

const result = trampoline(factorialTramped, 5); // 120

Когда задумываться о хвостовой рекурсии

• Редко в браузере — используй цикл
• В функциональных языках (Scheme, Haskell) — критично
• В JavaScript — лучше используй итерацию
• Для интервью — знай концепцию, но рекомендуй итерацию

Заключение

Хвостовая рекурсия — важная концепция, но в JavaScript:

• Не гарантирована TCO оптимизация
• Лучше использовать циклы или reduce/map
• Полезна в функциональных языках
• Хороший вопрос на интервью для проверки понимания рекурсии