Исходный код Рекурсия

Elixir не предоставляет конструкции циклов. Вместо этого мы используем рекурсию и высокоуровневые функции для работы со структурами данных. В этой главе мы рассмотрим первый подход.

Циклы с помощью рекурсии

Из-за неизменяемости циклы в Elixir (как и в любом функциональном языке программирования) записываются по-другому, чем в императивных языках. Например, на языке C:

for(i = 0; i < sizeof(array); i++) {
  array[i] = array[i] * 2;
}

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

defmodule Recursion do
  def print_multiple_times(msg, n) when n > 0 do
    IO.puts(msg)
    print_multiple_times(msg, n - 1)
  end

  def print_multiple_times(_msg, 0) do
    :ok
  end
end

Recursion.print_multiple_times("Hello!", 3)
# Hello!
# Hello!
# Hello!
:ok

Подобно case, функция может иметь множество определений. Определённое определение выполняется, когда переданные в функцию аргументы соответствуют шаблонам аргументов этого определения, а условия (guards) вычисляются как true.

Когда print_multiple_times/2 вызывается в примере выше, аргумент n равен 3.

В первом определении есть условие (guard), которое гласит: «используйте это определение только тогда, когда n больше, чем 0». Поскольку это условие выполняется, оно выводит msg и затем вызывает само себя, передавая n - 1 (2) в качестве второго аргумента.

Теперь мы снова выполняем эту функцию, начиная с первого определения. Учитывая, что второй аргумент, n, по-прежнему больше 0, мы выводим сообщение и снова вызываем себя, теперь со вторым аргументом, равным 1. Затем мы выводим сообщение в последний раз и вызываем print_multiple_times("Hello!", 0), снова начиная с начала.

Когда второй аргумент равен нулю, условие (guard) n > 0 вычисляется как ложь, и первое определение функции не выполняется. Elixir затем переходит к следующему определению функции, которое явно соответствует случаю, когда n равно 0. Это определение, также известное как определение завершения, игнорирует аргумент сообщения, присваивая его переменной _msg, и возвращает атом :ok.

Наконец, если вы передадите аргумент, который не соответствует ни одному определению, Elixir генерирует исключение FunctionClauseError:

iex> Recursion.print_multiple_times "Hello!", -1
** (FunctionClauseError) no function clause matching in Recursion.print_multiple_times/2

    The following arguments were given to Recursion.print_multiple_times/2:

        # 1
        "Hello!"

        # 2
        -1

    iex:1: Recursion.print_multiple_times/2

Алгоритмы Reduce и Map

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

defmodule Math do
  def sum_list([head | tail], accumulator) do
    sum_list(tail, head + accumulator)
  end

  def sum_list([], accumulator) do
    accumulator
  end
end

IO.puts Math.sum_list([1, 2, 3], 0) #=> 6

Мы вызываем sum_list со списком [1, 2, 3] и начальным значением 0 в качестве аргументов. Мы будем проверять каждое определение, пока не найдём то, которое соответствует правилам сопоставления с образцом. В данном случае список [1, 2, 3] соответствует [head | tail], что связывает head с 1 и tail с [2, 3]; accumulator устанавливается в 0.

Затем мы добавляем голову списка к аккумулятору head + accumulator и снова рекурсивно вызываем sum_list, передавая хвост списка в качестве первого аргумента. Хвост будет снова соответствовать [head | tail] до тех пор, пока список не станет пустым, как показано ниже:

sum_list [1, 2, 3], 0
sum_list [2, 3], 1
sum_list [3], 3
sum_list [], 6

Когда список пустой, будет выполнено последнее определение, которое возвращает окончательный результат 6.

Процесс преобразования списка в одно значение называется алгоритмом reduce и является центральным в функциональном программировании.

А что, если мы хотим вместо этого удвоить все значения в нашем списке?

defmodule Math do
  def double_each([head | tail]) do
    [head * 2 | double_each(tail)]
  end

  def double_each([]) do
    []
  end
end

$ iex math.exs

iex> Math.double_each([1, 2, 3]) #=> [2, 4, 6]

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

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

Модуль Enum, который мы рассмотрим в следующей главе, уже предоставляет множество удобств для работы со списками. Например, примеры выше можно переписать так:

iex> Enum.reduce([1, 2, 3], 0, fn x, acc -> x + acc end)
6
iex> Enum.map([1, 2, 3], fn x -> x * 2 end)
[2, 4, 6]

Или, используя синтаксис захвата:

iex> Enum.reduce([1, 2, 3], 0, &+/2)
6
iex> Enum.map([1, 2, 3], &(&1 * 2))
[2, 4, 6]

Давайте более подробно рассмотрим Enumerable и, пока мы на этом, его ленивый аналог, Stream.