Рекурсия и хвостовые вызовы

В Elixir нет циклов for в привычном смысле — повторение выражают рекурсией. И это не страшно: BEAM умеет делать её без переполнения стека.

Рекурсия в функциональном языке — это не экзотика, а штатный способ перебора. Аккумулятор заменяет изменяемый счётчик.

Базовый приём — рекурсия с аккумулятором: вспомогательная функция несёт промежуточный результат:

defmodule Math do
  def sum(list), do: do_sum(list, 0)

  defp do_sum([], acc), do: acc
  defp do_sum([head | tail], acc), do: do_sum(tail, acc + head)
end

Math.sum([1, 2, 3, 4])   # => 10

Здесь рекурсивный вызов — последнее действие функции. Это и есть хвостовая рекурсия, и BEAM выполняет её в постоянной памяти, не наращивая стек.

# НЕхвостовая: после вызова ещё есть работа (+ head)
def sum([head | tail]), do: head + sum(tail)

# Хвостовая: вызов — последнее действие, стек не растёт
defp do_sum([head | tail], acc), do: do_sum(tail, acc + head)

Как работает под капотом (BEAM)

Когда рекурсивный вызов стоит в хвостовой позиции (это самое последнее, что делает функция), BEAM применяет оптимизацию хвостового вызова: вместо создания нового стекового кадра она переиспользует текущий. Фактически хвостовая рекурсия превращается в цикл, работающий в константной памяти — можно складывать список из миллионов элементов без переполнения. В нехвостовом варианте каждый вызов оставляет «отложенную работу» (например, head + ...), поэтому кадры копятся. Парадокс: иногда нехвостовой код на BEAM работает не медленнее благодаря оптимизациям, но для очень больших данных хвостовая форма надёжнее.

  Хвостовая do_sum([1,2,3], 0):
    do_sum([1,2,3], 0)
    do_sum([2,3],   1)   стек НЕ растёт —
    do_sum([3],     3)   тот же кадр переиспользуется
    do_sum([],      6) -> 6

Та же идея на Python ▶

Python не оптимизирует хвостовые вызовы, но идею аккумулятора показать легко; для глубины используем итеративный вариант.

# Рекурсия с аккумулятором (как do_sum)
def do_sum(items, acc=0):
    if not items:               # do_sum([], acc) -> acc
        return acc
    head, *tail = items
    return do_sum(tail, acc + head)

print(do_sum([1, 2, 3, 4]))     # 10

# Эквивалент "хвостовой рекурсии" в Python — цикл с аккумулятором
def sum_iter(items):
    acc = 0
    for x in items:             # BEAM сделал бы это рекурсией в конст. памяти
        acc += x
    return acc

print(sum_iter(range(1, 1_000_001)))   # 500000500000

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

• Забыть базовый случай. Без клаузы для [] рекурсия не остановится.
• Считать любую рекурсию хвостовой. Если после вызова есть операция (head + sum(...)) — она нехвостовая.
• Изобретать рекурсию там, где есть Enum. Для типовых обходов Enum.reduce читаемее ручной рекурсии.

Best practices

• Для собственных обходов используйте аккумулятор и хвостовую форму.
• Прячьте аккумулятор в приватной do_*-функции, оставляя чистый публичный API.
• Не пишите рекурсию, если задачу решает готовая функция Enum/Stream.

Итог. Рекурсия с аккумулятором заменяет циклы, а хвостовая оптимизация BEAM делает её безопасной даже на огромных данных. Понимание этого готовит к работе с потоками данных и, главное, к процессам, чьи циклы обработки сообщений — тоже хвостовая рекурсия.

Аккумулятор как замена изменяемому состоянию

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

Стоит знать и о практической стороне на BEAM. Благодаря оптимизации хвостовых вызовов рекурсия с аккумулятором в хвостовой позиции работает в постоянной памяти — это и есть тот самый «цикл» Elixir, на котором, к слову, крутятся все серверные процессы: их главный loop — это бесконечная хвостовая рекурсия, переиспользующая один кадр стека годами. Так что, осваивая рекурсию с аккумулятором сейчас, вы готовите себя к пониманию того, как устроены долгоживущие процессы в следующих разделах.