Рекурсия — это механизм, при котором функция вызывает саму себя для решения подзадачи. Это основной способ реализации повторяющихся операций в функциональных языках программирования, таких как Elixir, где отсутствуют привычные императивные конструкции for, while и переменные-счётчики. Вместо них используются рекурсивные вызовы и сопоставление с образцом (pattern matching).

Что происходит при рекурсии

Рекурсивная функция должна:

1. иметь условие завершения (базовый случай) — чтобы остановить вызовы;

2. вызывать себя с новым, изменённым аргументом — для продвижения к завершению;

3. возвращать результат — или аккумулировать его через параметры.

Пример простейшей рекурсии: сумма списка

defmodule Utils do
def sum(\[\]), do: 0
def sum(\[head | tail\]), do: head + sum(tail)
end

Разбор:

• Базовый случай — пустой список [], сумма которого равна 0.

• Рекурсивный случай — добавление первого элемента (head) к сумме оставшихся (tail).

• На каждом шаге список уменьшается, приближаясь к базовому случаю.

Как рекурсия заменяет цикл

В императивных языках:

sum = 0
for i in list do
sum = sum + i
end

В функциональных:

Utils.sum(list)

Всё, что делал цикл — шаг за шагом аккумулировал значение — теперь делает рекурсивная функция.

Хвостовая рекурсия

Elixir (и BEAM) поддерживает хвостовую рекурсию (tail recursion) — оптимизацию, при которой функция не создает новый стек вызова, если последний шаг — это вызов самой себя. Это позволяет писать рекурсивные функции, не боясь переполнения стека.

Пример с хвостовой рекурсией:

defmodule Utils do
def sum_tail(list), do: sum_tail(list, 0)
defp sum_tail(\[\], acc), do: acc
defp sum_tail(\[head | tail\], acc), do: sum_tail(tail, acc + head)
end

Здесь acc — аккумулятор, который накапливает результат. После последнего вызова стек очищается, не накапливая слои.

Пример: подсчёт длины списка

def length(\[\]), do: 0
def length(\[_ | tail\]), do: 1 + length(tail)

Аналог Enum.count/1, но через рекурсию.

Пример: map — применить функцию к каждому элементу списка

def map(\[\], \_func), do: \[\]
def map(\[head | tail\], func), do: \[func.(head) | map(tail, func)\]

Аналог Enum.map/2.

Пример: фильтрация значений

def filter(\[\], \_func), do: \[\]
def filter(\[head | tail\], func) do
if func.(head) do
\[head | filter(tail, func)\]
else
filter(tail, func)
end
end

Работает как Enum.filter/2.

Рекурсия с несколькими аргументами

Когда нужно обрабатывать два списка одновременно:

def zip(\[\], \[\]), do: \[\]
def zip(\[h1 | t1\], \[h2 | t2\]), do: \[{h1, h2} | zip(t1, t2)\]

Рекурсивная реализация reduce

def reduce(\[\], acc, \_func), do: acc
def reduce(\[head | tail\], acc, func), do: reduce(tail, func.(head, acc), func)

Почему рекурсия — основной способ повторений в Elixir

• Отсутствие мутабельных переменных исключает возможность изменять значения внутри цикла.

• Отказ от императивных конструкций делает циклы невозможными.

• Рекурсия позволяет описывать логику без состояния.

• Сопоставление с образцом делает разбор структуры данных простым и безопасным.

Где особенно удобна рекурсия

• При обработке вложенных структур (списки списков, деревья)

• При реализации собственных итераторов

• Для построения чистых функций без побочных эффектов

Рекурсия позволяет выразить повторяющуюся логику элегантно, структурировано и безопасно. С опытом её использование становится привычным способом мыслить в Elixir и других функциональных языках.