Хвостовая рекурсия (tail recursion) — это форма рекурсии, при которой рекурсивный вызов функции является последней операцией в теле функции. Это позволяет виртуальной машине (в случае Elixir — BEAM) не накапливать стек вызовов, а просто переиспользовать текущий стековый фрейм, что обеспечивает высокую производительность и предотвращает переполнение стека при большом числе итераций.

Основная идея хвостовой рекурсии

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

Пример обычной (нехвостовой) рекурсии

defmodule Recursion do
def sum(\[\]), do: 0
def sum(\[head | tail\]), do: head + sum(tail)
end

Здесь выражение head + sum(tail) требует дождаться результата sum(tail), чтобы завершить сложение. Это не хвостовая рекурсия.

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

Чтобы сделать функцию хвосторекурсивной, нужно добавить дополнительный параметр — аккумулятор. В него мы будем накапливать промежуточный результат.

defmodule Recursion do
def sum(list), do: sum(list, 0)
defp sum(\[\], acc), do: acc
defp sum(\[head | tail\], acc), do: sum(tail, acc + head)
end

Здесь:

• sum(list) — внешний интерфейс.

• sum(list, acc) — хвостовая рекурсивная функция.

• acc — аккумулятор (накопитель), который передаётся от шага к шагу.

Объяснение на уровне вызовов

Пример списка [1, 2, 3]:

sum(\[1,2,3\])
\-> sum(\[2,3\], 1)
\-> sum(\[3\], 3)
\-> sum(\[\], 6)
\-> 6

Никаких возвращений назад: каждый вызов переходит сразу к следующему.

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

Факториал

defmodule Math do
def factorial(n), do: factorial(n, 1)
defp factorial(0, acc), do: acc
defp factorial(n, acc), do: factorial(n - 1, acc \* n)
end

Подсчёт длины списка

defmodule Length do
def count(list), do: count(list, 0)
defp count(\[\], acc), do: acc
defp count(\[\_head | tail\], acc), do: count(tail, acc + 1)
end

Разворот списка

defmodule Utils do
def reverse(list), do: reverse(list, \[\])
defp reverse(\[\], acc), do: acc
defp reverse(\[head | tail\], acc), do: reverse(tail, \[head | acc\])
end

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

В Elixir и Erlang хвостовая рекурсия не требует ручного включения оптимизаций — BEAM оптимизирует её автоматически, но только если рекурсивный вызов находится в позиции хвоста (последнее действие в теле функции). Это ключевое условие: нельзя писать что-то после вызова функции, иначе оптимизация не сработает.

Пример (неоптимизируемо):

def sum(\[head | tail\], acc), do: acc + sum(tail, head) # НЕЛЬЗЯ

Так писать нельзя, потому что + требует результата от sum, а значит стек будет сохраняться.

Тестирование производительности

Хвостовая рекурсия позволяет безопасно работать с большими объёмами данных:

list = Enum.to_list(1..100_000)
Recursion.sum(list)

Обычная рекурсия в этом случае может вызвать SystemStackError, а хвостовая — нет.

Оптимизация через :tailrec модуль

Elixir сам не предлагает встроенных директив для контроля хвостов, но существуют библиотеки (например, TailRec), которые помогают структурировать хвостовые вызовы в более читаемом виде, особенно когда структура рекурсии сложная.

Отличие от Enum.reduce

Хвосторекурсивные функции часто соответствуют Enum.reduce/3:

Enum.reduce(\[1,2,3\], 0, fn x, acc -> x + acc end)

Это делает reduce универсальным API, но при необходимости вы можете реализовать собственный аналог с полной контролируемостью.

Хвостовая рекурсия — важный инструмент Elixir-разработчика. Она используется повсеместно: от стандартных модулей (например, Enum) до внутренних реализаций циклических операций в своих библиотеках и проектах.