Хвостовая рекурсия в Erlang'e

Хвостовая рекурсия - это рекурсия только с одним рекурсивным вызовом, когда функция вызывает саму себя только в конце своего выполнения (хвостовой вызов). Все остальные рекурсивные вызовы преобразуются в итерации - оптимизация хвостовой рекурсии. Так экономятся ресурсы на использовании стека вызовов - при увеличении глубины рекурсии, память не растет линейно, а остается постоянной. Это очень важно для Erlang'а, где циклы реализуются только через рекурсию. Но не смотря на важность, оптимизация хвостовой рекурсии выполняется только если рекурсивный вызов является последней операцией в функции, поэтому для следующей функции оптимизация не будет выполнена:

%% Сумма элементов списка
sum([]) -> 0;
sum([H|T]) ->
    %% последняя операция - "+"
    H + sum(T).

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

sum(X) -> 
    sum(X, 0).
%% Результат каждой итерации
%% складывается в Acc
sum([], Acc) ->
    Acc;
sum([H|T], Acc) ->
    %% хвостовой вызов
    sum(T, H + Acc).

sum/1 и sum/2 - это разные функции, поэтому определение sum/1 отделяется точкой, в противном случае при компиляции вылезет ошибка "head mismatch".

Существует мнение, что хвостовая рекурсия выполняется значительно быстрее, чем "обычная", но исходя из мифов об Эрланге, it depends.

Дополнительно о хвостовой рекурсии можно почитать:
- Recursion;
- A Deeper Look at Tail Recursion in Erlang;
- Erlang, Tail Recursion, and Living the Dream;
- Adventures in F#--Tail Recursion in Three Languages.