воскресенье, 29 ноября 2009 г.

Хвостовая рекурсия в 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.

5 комментариев:

jkff комментирует...

Хвостовая рекурсия и даже взаимная хвостовая рекурсия - это полная фигня, почти бесполезная фича, которую запросто можно заменить на цикл. Тем более что кое-какие "циклы" в эрланге есть - list comprehensions.

А вот хвостовые вызовы это совершенно иное дело. Это - самая натуральная языковая Фича, без которой некоторые стили программирования, в т.ч. постоянно используемые в эрланге, невозможны или уродливы.

Почитайте:
http://funcall.blogspot.com/2009/04/you-knew-id-say-something.html
http://funcall.blogspot.com/2009/04/you-knew-id-say-something-part-ii.html
http://funcall.blogspot.com/2009/05/you-knew-id-say-something-part-iii.html
http://funcall.blogspot.com/2009/05/you-knew-id-say-something-part-iv.html
http://funcall.blogspot.com/2009/05/you-knew-id-say-something-part-v.html

И по ссылкам оттудова походите.

sash_ko комментирует...

Чесно говоря единстенное отличие хвостовой рекурсии (ХР) от хвостового вызова (ХВ) которое я пока вижу (еще не успел почитать статью по вашим ссылкам), это вызов функцией самой себя, т.е. ХР - это частный случай ХВ. Да, сама по себе ХР - полная фигня, если нет оптимизации ХР, это хотя бы позволяет избежать переполнения стека.

Мои познания в эрланге довольно ограниченные, но я очень сомневаюсь, что все "циклические задачи" можно решить при помощи list comprehensions, по крайне мере это будет уродливо. Например, как реализовать тот же quick sort?

jkff комментирует...

Да, ХР - частный случай ХВ. Отличие состоит в том, что ХР как языковая фича - недостаточно обща, чтобы быть полезной, поэтому рассуждая о фичах языка, следует говорить о том, есть ли у него ХВ, а не просто ХР.

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

Но в общем я, конечно, не утверждаю, что все можно сделать comprehension'ами. Я просто напомнил, что то, что можно сделать ими - лучше делать ими, т.к. это гораздо читаемей, чем рекурсия. Ее вообще в любом ФЯ следует по возможности избегать и абстрагировать в комбинаторы высшего порядка.

sash_ko комментирует...

Мне кажется, я понял вашу точку зрения. В контексте большинства языков, где "явные" циклы - это обычное явление, ХР действительно бесполезная фича, без которой не сложно обойтись.

Про quicksort я упомянул как раз потому, что он часто используется для тренировок и экспериментов ;)

блоггер комментирует...

3 фильма, которые стоит посмотреть http://photorai.blogspot.com/2011/10/3.html