Рекурсия — вызов функцией самой себя. То же: recursion.
В Эрланге, как функциональном языке программирования, большое значение имеет рекурсия. Она позволяет при переборе списков не заводить временные переменные. Промежуточные значения хранятся в памяти без привязки к временным переменным. Эти значения в качестве аргументов передаются при каждом новом вызове функции.
Напишем и запустим такой вот скрипт:
#!/usr/bin/escript
main(_Arg) ->
Summa = sklad(1000),
io:format("~p~n", [Summa]).
sklad(0) -> 0;
sklad(N) -> N + sklad(N-1).
Функция sklad/1 является типичной рекурсивной функцией, которая вызывает саму себя. В принципе, все рекурсивные функции похожи друг на друга. В каких-то кляузах функции вызывают сами себя, а в каких-то этот процесс погружения в пучину останавливается и начинается подъём назад.
После этого происходит подъём наверх, и каждый вызов функции получает нужные ему аргументы. И там, где было 1000 + sklad(999), станет 1000 + 499500. Ну и итог всего — 500500.
Опытный программист сразу заметит возможные проблемы с нашей функцией sklad/1. Во-первых, если подать в качестве аргумента отрицательную величину, это вызовет нескончаемую рекурсию. N будет всё уменьшаться и уменьшаться, но никогда не достигнет значения 0, на котором рекурсия должна была бы остановиться. Программа будет какое-то время выполняться, а потом вылетит с сообщением “Out of memory”.
Погружение в пучину рекурсии не может быть бесконечным. С каждым новым уровнем рекурсии данных становится всё больше и больше. И они начинают довлеть всё более тяжёлым грузом.
Во-вторых, то же самое (нехватка памяти) случится, если мы подадим слишком большую величину в качестве аргумента. На моей машине 2_750_000 можно подать, а 2_800_000 — уже нет.
Два миллиона уровней рекурсии это хорошо, но всё равно внушает опасения: а вдруг у нас в какой-то последовательности окажется три миллиона элементов? К счастью, в Эрланге есть прекрасная вещь под названием хвостовая рекурсия. С её помощью действительно можно перебирать бесконечное количество элементов. С её помощью функция в акторе может раз за разом себя вызывать после срабатывания оператора receive (обработка входящих сообщений).
© Алексей Карманов, 2024.