Хвостовая рекурсия — рекурсия, которая может происходить бесконечно. То же: tail recursion.
При обычной рекурсии функция в своём теле вызывает саму себя и при этом ожидает результата. Возьмём в качестве примера код, который на моём компьютере не выполняется:
#!/usr/bin/escript
main(_Arg) ->
Summa = sklad(2_800_000),
io:format("~p~n", [Summa]).
sklad(0) -> 0;
sklad(N) -> N + sklad(N-1).
А не выполняется он потому, что ему не хватает памяти для 2_800_000 уровней рекурсии. Главная идея хвостовой рекурсии — надо сделать так, чтобы не было никаких уровней погружения в рекурсию, чтобы при каждом новом вызове функции расход памяти не увеличивался. То есть сделать так, чтобы от вызова к вызову значения передавались по цепочке. Первый вызов функции не должен ждать результатов от других вызовов.
Значит, включаем мы логику, в качестве аргумента нам придётся передавать ещё кое-что, а именно текущую сумму (для нашего примера). К сожалению, арность функции sklad придётся увеличить на одно значение.
#!/usr/bin/escript
main(_Arg) ->
Summa = sklad(100_000_000, 0),
io:format("~p~n", [Summa]).
sklad(0, S) -> S;
sklad(N, S) -> sklad(N-1, S+N).
Была sklad/1, а стала sklad/2. Зато теперь можно суммировать не только 3 миллиона чисел, но, если угодно, 3 миллиарда. Правда, если вы запустите этот скрипт, то получите, что он очень долго выполняется. Если скомпилировать, то будет гораздо быстрее.
Первый аргумент у функции sklad — текущее число (сначала 100_000_000, потом 99_999_999 и т.д). Второй аргумент — текущая сумма чисел. Два аргумента передаются по цепочке. Один постепенно убывает (текущее число), второй постепенно растёт, вбирая в себя все те числа N, которые до этого встретились. Как только текущее число достигнет значения 0, вступит в силу первая кляуза, которая просто вернёт сумму. И из всей этой длинной вереницы вызовов вернётся именно это последнее значение. Очень просто и эффективно.
Но возникает резонный вопрос: а чем принципиально отличается кляуза sklad(N) -> N + sklad(N-1)
из первого примера от кляузы sklad(N, S) -> sklad(N-1, S+N)
из второго? А вы попробуйте последнюю строчку второй версии программы переписать так:
sklad(N, S) -> 1 + sklad(N-1, S+N).
Вроде бы просто добавляем единицу, но программа опять будет вылетать с ошибкой из-за нехватки памяти. Дело в том, что на каждом промежуточном этапе выражение 1 + sklad(N-1, S+N)
не может быть рассчитано, чтобы получить его значение. Значит, это выражение должно сохраниться в памяти и быть рассчитанным потом.
Другое дело выражение sklad(N-1, S+N)
. Оно, конечно, прямо сейчас тоже не может быть вызвано. Но это и не требуется. Эрланг просто делает новый вызов функции sklad/2 с этими двумя аргументами. Остальное уже не важно. Хвостовая рекурсия так называется, потому что в конце кляузы функция просто сама себя вызывает, не оставляя никаких следов предыдущего вызова.
Пусть в этой цепочке будет даже 100 миллионов вызовов функции, когда будет последний вызов, его результат и будет итоговым.
Вот так НЕЛЬЗЯ делать:
sklad(0, S) -> S;
sklad(N, S) ->
sklad(N-1, S+N),
math:pi().
Сам по себе этот пример абсурдный, потому что в любом случае функция в итоге вернёт число Пи. А если входной аргумент окажется слишком большим, то программа завершится крахом. Хвостовая рекурсия потому и называется хвостовой, раз вызов самой себя может быть только в самом конце кляузы. Иначе память будет забиваться.
В нашей программе есть ещё одна проблема — в этой строке:
Summa = sklad(100_000_000, 0),
Чтобы получить верный результат, второй аргумент всегда должен быть 0. Если мы лишь учимся программировать или пишем утилиту, которая просуществует день-два, это не проблема. Но если мы пишем настоящую функцию, которую будем использовать через год или через пять лет, причём совсем из другого модуля, это может вызвать проблему.
Второй аргумент — чисто технический. В АПИ он не нужен и даже опасен. Как же тогда быть?
Придётся создать ещё одну функцию — оболочку над рекурсивной. Это не такая уж большая жертва.
main() ->
Summa = sklad(1_000_000),
io:format("~p~n", [Summa]).
sklad(N) -> sklad2(N, 0).
sklad2(0, S) -> S;
sklad2(N, S) ->
sklad2(N-1, S+N).
Фактически мы добавили всего одну строку.
Актор спаунится как задание (некоторая функция или фунтерм с аргументами), задание выполняется (допустим, удалить некоторый файл), актор прекращает свою работу.
Но другим акторам для полноценной работы может понадобиться получать сообщения от других акторов. Допустим, в этом акторе мы держим открытую базу данных, в неё заносим информацию, которую получаем от других акторов, которую проверяем и как-то форматируем.
Как нам зациклить в этом акторе процесс проверки почтового ящика и совершения некоторых операций со входящими сообщениями? Здесь нам тоже приходит на помощь хвостовая рекурсия. Сама по себе эта рекурсивная функция ничего из актора не возвращает (актор это не функция и не возвращает значения), но она нужна для зацикливания.
Давайте создадим актор, который просматривает все входящие сообщения и ищет те, которые состоят лишь из одного атома privet. В этом случае он сохраняет в Dets-таблице время, когда с ним поздоровались, а также сам атом privet. Также он в ответ тоже здоровается. Если пришло какое-то иное сообщение, он на него никак не реагирует.
В принципе, мы бы могли сделать так, что при каждой новой итерации, вызванной новым сообщением, мы бы открывали Dets-таблицу, писали (или не писали) бы в неё данные, а потом закрывали. Но это неправильно, потому что создаёт избыточную нагрузку на Систему. К тому же нам, весьма вероятно, перед запуском бесконечного цикла захочется выполнить какую-то конфигурацию актора. Например, сделать какое-то сложное вычисление, отправить кому-то email или же заспаунить ещё акторов.
Поэтому общий подход такой: сначала мы спауним одну функцию (назовём её start), она как-то конфигурирует актор, а потом (в самом конце) запускает функцию с хвостовой рекурсией, которая, сделав что-то, снова запускает саму себя.
-module(aktor).
-export([start/0]).
start() ->
io:format("Starting...~n"),
{ok,Dets} = dets:open_file(?MODULE, []),
loop(Dets).
loop(Dets) ->
io:format("New iteration...~n"),
receive
privet ->
dets:insert(Dets, {erlang:system_time(), privet}),
io:format("Hello you!~n"),
loop(Dets);
_ ->
loop(Dets)
end.
Когда актор запускается, то он выводит сообщение “Starting…”. Далее открывается Dets-таблица, ссылка на неё привязывается к переменной Dets. Внутри loop() понадобится эта переменная, поэтому мы запускаем рекурсивную функцию, передавая ей аргумент Dets. Далее будет ещё два вызова loop/1. И в обоих, конечно, надо передать тот же аргумент Dets, чтобы он никуда не пропал из итераций.
При каждой новой итерации выводится сообщение “New iteration…”. Далее заступает на боевое дежурство оператор receive ... end
. Этот оператор может выполняться очень долго: секунды, минуты, часы, дни… — пока не получит сообщение. Получив privet, он записывает в БД, тоже здоровается и запускает loop(Dets). Наступает новый вызов функции loop/1, а старый исчез в небытие.
Это тоже хвостовая рекурсия. Актор может обработать хоть миллиард сообщений, и всё равно переполнения стека не будет.
Если пришло иное какое-то сообщение, то сразу срабатывает loop(Dets). Таким образом, в любом случае loop/1 вызовет саму себя и по цепочке передаст новому вызову аргумент Dets. Если в одной или обеих кляузах забыть вставить вызов loop/1, то в этом месте цепочка прервётся, последний вызов loop будет завершён, завершится и работа всего актора.
Конечно, это может быть так задумано — что при одних обстоятельствах рекурсия продолжается (функция продолжает вызывать саму себя), а при других обстоятельствах рекурсия прекращается, и актор завершает свою работу. Поэтому совсем не обязательно во всех ветках вставлять loop().
Скомпилируем и проверим работу актора в оболочке:
1> A = spawn(aktor, start, []).
Starting...
<0.83.0>
New iteration...
2> A ! privet.
privet
Hello you!
New iteration...
3> A ! poka.
New iteration...
poka
4> A ! privet.
Hello you!
New iteration...
privet
Как мы видим, всё прошло по плану.
© Алексей Карманов, 2024.