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

Как Erlang повторяет действия без циклов for и while.

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

В Erlang нет циклов for и while. Повторение выражается рекурсией — функция вызывает саму себя. Поначалу это пугает, но в функциональном языке это естественно и, при правильном подходе, эффективно. Причина отсутствия циклов глубже, чем кажется: обычный цикл держится на изменяемом счётчике, который меняется на каждом обороте. А в Erlang переменные неизменяемы, поэтому «переменной цикла», которую можно увеличивать, просто неоткуда взяться. Рекурсия решает ту же задачу иначе — каждый повтор это новый вызов функции с новыми значениями аргументов, и никакая ячейка памяти при этом не перезаписывается.

Чтобы перестать бояться рекурсии, полезно держать в голове универсальный рецепт. Сначала опишите базовый случай — ситуацию, когда повторять больше нечего и можно вернуть готовый ответ. Затем опишите шаг — как свести задачу к чуть меньшей такой же задаче и что сделать с «отрезанным» куском. Для списка базовый случай это обычно пустой список, а шаг — обработать голову и рекурсивно заняться хвостом. Стоит увидеть эту пару «база плюс шаг» несколько раз, и рекурсивные определения начнут писаться почти автоматически.

Обычная рекурсия

Классический пример — сумма списка. Описываем два случая: пустой список и список с головой. Эти два случая идеально ложатся на две клаузы функции с разными шаблонами — здесь снова видно, как pattern matching из прошлых уроков становится рабочей лошадкой рекурсии.

sum([]) -> 0;
sum([H | T]) -> H + sum(T).

Здесь каждый вызов ждёт результата следующего, чтобы прибавить H. Для длинного списка это создаёт глубокий стек отложенных операций — потенциальная проблема памяти. Проследим мысленно за вычислением суммы списка из трёх чисел: первый вызов не может сложить ничего, пока не узнает сумму хвоста, тот ждёт сумму своего хвоста, и так до самого конца. Лишь достигнув пустого списка и получив ноль, цепочка начинает «схлопываться» обратно, выполняя отложенные сложения в обратном порядке. Все эти «недоделанные» сложения всё это время висят в стеке.

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

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

Перепишем так, чтобы рекурсивный вызов был последним действием. Промежуточный результат накапливаем в дополнительном аргументе — аккумуляторе. Идея в том, чтобы выполнять сложение не на «обратном ходе», а сразу, по пути вперёд: к моменту, когда мы доходим до конца списка, ответ уже полностью готов в аккумуляторе, и его остаётся только вернуть.

sum(List) -> sum(List, 0).

sum([], Acc) -> Acc;
sum([H | T], Acc) -> sum(T, Acc + H).

Теперь после вызова sum(T, Acc + H) делать больше нечего — это и есть хвостовой вызов. BEAM не наращивает стек: он переиспользует текущий кадр. Функция работает в постоянной памяти даже для миллиона элементов. Обратите внимание на маленькую, но принципиальную разницу: сложение Acc + H вычисляется до рекурсивного вызова и передаётся ему готовым числом, тогда как в обычной версии сложение стояло снаружи вызова и ждало его результата. Перенос работы внутрь аргумента — и есть весь секрет превращения рекурсии в хвостовую.

Заметьте также приём с двумя версиями функции: публичная sum/1 с одним аргументом просто запускает рабочую sum/2 с начальным значением аккумулятора. Это типичная для Erlang пара «обёртка плюс рабочая лошадка»: наружу торчит удобный интерфейс без лишнего аргумента, а вся механика с аккумулятором спрятана внутри. Благодаря тому, что функции различаются по арности, обе спокойно носят одно имя.

Сравним поведение

Глядя на таблицу, легко решить, что хвостовую рекурсию надо использовать всегда. На практике это не догма. Для коротких заведомо ограниченных списков обычная рекурсия часто читается яснее и не требует возни с аккумулятором и финальным переворотом. Опытный разработчик выбирает хвостовую форму там, где данные могут быть большими или цикл должен жить вечно, и не усложняет код там, где в этом нет нужды. Иными словами, хвостовая рекурсия — это инструмент под конкретную потребность, а не обязательный ритуал.

Накопление списка и переворот

При хвостовой рекурсии новые элементы удобно добавлять в голову аккумулятора (это дёшево), а в конце один раз перевернуть результат. Причина в устройстве списков Erlang: добавить элемент в начало списка — мгновенная операция, ведь достаточно создать новую ячейку, указывающую на старый список. А вот дописать в конец — дорого, потому что пришлось бы пройти весь список до хвоста. Поэтому идиоматичный приём такой: накапливаем результат «задом наперёд», добавляя в голову, и один-единственный раз в самом конце переворачиваем готовый список.

double_all(List) -> double_all(List, []).

double_all([], Acc) -> lists:reverse(Acc);
double_all([H | T], Acc) -> double_all(T, [H * 2 | Acc]).

Как работает под капотом

Когда компилятор видит, что рекурсивный вызов — последнее выражение клаузы, он применяет оптимизацию хвостового вызова (tail call optimization): вместо создания нового стекового кадра он переиспользует текущий. По сути цикл выражается как функция, но выполняется как итерация. Долгоживущие процессы Erlang (например, серверы) обычно построены на бесконечной хвостовой рекурсии — именно поэтому они не «текут» по памяти. Ключевое условие оптимизации — вызов обязан стоять в позиции последнего действия буквально, без всякой обёртки. Если результат рекурсивного вызова куда-то передаётся, складывается или сравнивается, вызов перестаёт быть хвостовым, и оптимизация не срабатывает.

Этот механизм объясняет, почему в Erlang спокойно пишут процессы, которые «крутятся» месяцами без перезапуска. Серверный цикл вызывает сам себя в хвостовой позиции на каждом обороте, обрабатывая очередное сообщение, и при этом не накапливает ни байта лишней памяти. Получается вечный цикл, выраженный рекурсией, но исполняемый как обычная итерация — фундамент, на котором стоит почти вся конкурентная архитектура языка, к которой мы перейдём в следующем разделе.

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

• Считать любую рекурсию хвостовой. Если после вызова есть операция (как H + sum(T)) — она не хвостовая.
• Забыть базовый случай. Без условия остановки рекурсия не завершится.
• Добавлять в хвост аккумулятора через ++. Это медленно; копите в голову и переверните.

Итоги

• В Erlang повторение выражается рекурсией, а не циклами.
• Хвостовая рекурсия (вызов — последнее действие) работает в постоянной памяти.
• Аккумулятор переносит промежуточный результат и делает рекурсию хвостовой.
• Долгоживущие процессы Erlang основаны на бесконечной хвостовой рекурсии.