Хвостовая рекурсия — рекурсия, которая может происходить бесконечно. То же: 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.