Статьи

Erlang: функции (часть 2)

Сентябрь 8, 2018

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

Стек

Давайте возьмем определение факториала с прошлой недели:

recursive_factorial(0) -> 1;
recursive_factorial(N) -> recursive_factorial(N - 1) * N.

Мы повторяем N раз, где N — число, переданное при первом обращении к recursive_factorial / 1. Только когда N равно 0, первое предложение сопоставляется и рекурсия останавливается; после этого каждый вызов recursive_factorial (0), recursive_factorial (1), … возвращается, и его результат умножается на аргумент N, хранящийся в памяти до тех пор.

Вы, вероятно, знаете, что все вызовы функций накапливаются в стеке, структуре данных, в которой последний вставленный элемент всегда извлекается первым. В случае recursive_factorial / 1 стек выглядит так:

factorial(0) -> % now I'll return 1
factorial(1) -> local: N = 1
factorial(2) -> local: N = 2
factorial(3) -> local: N = 3

когда мы вычисляем recursive_factorial (3) и мы находимся в recursive_factorial (0), конечно.

Проблема с такого рода рекурсией заключается в том, что вы можете исчерпать пространство стека, * особенно *, если функция будет непрерывно выполняться и вызываться сама, как основной цикл. В C ++ вы могли бы написать:

while (1) {
    // wait for input, do something
}

но в Эрланге то же самое делается с функциями:

main() ->
    // wait for input, do something
    main().

было бы невозможно без хвостовой рекурсии. Трассировка стека будет расти на каждой итерации, пока у нас не закончится память.

От прямой рекурсии к хвостовой рекурсии

Определение хвостового вызова в Erlang:


Последний оператор выполнения функции, чье возвращаемое значение становится возвращаемым значением исходной функции.

Например, в:

a() ->
    b(),
    c().

c () — это хвостовой вызов, а b () — нет. Если мы написали:

a(A) ->
    b(),
    A * c().

c () не будет хвостовым вызовом, потому что его возвращаемое значение должно быть обработано, чтобы стать возвращаемым значением (A).

Когда хвостовой вызов указывает на саму функцию, он является экземпляром хвостовой рекурсии. Давайте перепишем recursive_factorial:

tail_factorial(N) -> tail_factorial(1, N).

tail_factorial(N, 0) -> N;
tail_factorial(Result, N) -> tail_factorial(Result * N, N - 1).

simple_test() ->
    ?assertEqual(6, tail_factorial(3)),
    ?assertEqual(2, tail_factorial(2)),
    ?assertEqual(1, tail_factorial(1)),
    ?assertEqual(1, tail_factorial(0)).

Мы используем переменную Result, как в цикле for ():

for (int I = N; I > 0; I--) {
    Result = Result * I;
} // this is not Erlang code

Когда мы вызываем tail_factorial (3), стек теперь выглядит так:

factorial(6, 0) -> % now I'll return 6
factorial(6, 1) ->
factorial(3, 2) ->
factorial(1, 3) ->
factorial(3) ->

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

factorial(6, 0) -> % now I'll return 6
factorial(3) ->

factorial (6, 0) будет напрямую возвращать свой результат факториалу (3). Хвостовые рекурсивные вызовы могут перезаписать предыдущий вызов той же функции в стеке, и никто об этом не заметит.

Итак, наш основной цикл:

main() ->
    // wait for input, do something
    main().

теперь может фактически работать вечно, не исчерпывая стек.

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

Больше примеров, пожалуйста

Давайте реализуем функцию zip / 2. Он уже существует в модуле списков как lists: zip, но это хорошее упражнение для хвостовой рекурсии.

Вот что делает zip:

    ?assertEqual([],
        zip([], [])),
    ?assertEqual([{a, 'alpha'}],
            zip([a], ['alpha'])),
    ?assertEqual([{a, 'alpha'}, {b, 'bravo'}, {c, 'charlie'}],
            zip([a, b, c], ['alpha', 'bravo', 'charlie'])).

Вот реализация с хвостовой рекурсией. У нас все еще есть одна переменная-накопитель Result, но два аргумента для передачи.

zip(First, Second) -> zip([], First, Second).

zip(Result, [], []) -> Result;
zip(Result, [FirstHead|FirstTail], [SecondHead|SecondTail]) ->
    zip(Result ++ [{FirstHead, SecondHead}], FirstTail, SecondTail).

К настоящему времени вы можете увидеть шаблон:

  • исходная функция выполняет инициализацию .
  • Функция с дополнительным аргументом аккумулятора выполняет шаг итерации и перезапускает себя.

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

average_test() ->
    ?assertEqual(2.0, average([2])),
    ?assertEqual(2.0, average([1, 3])),
    ?assertEqual(2.0, average([1, 3, 1, 1, 1, 5])).

Erlang имеет функцию длины, но давайте построим среднее значение / 1 с помощью хвостовой рекурсии:

average(Numbers) ->
    {Total, Size} = average(0, 0, Numbers),
    Total / Size.

average(Total, Size, []) -> {Total, Size};
average(Total, Size, [Head|Tail]) ->
    average(Total + Head, Size + 1, Tail).

Выводы

Хвостовая рекурсия — это другой способ реализации рекурсии, и в Erlang она необязательна для реализации алгоритмов. Тем не менее, это является обязательным, когда речь идет о создании циклов, таких как функция main / 0.

Весь код, который я написал в этой статье, доступен в репозитории Github для этой серии .

64
Share: