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

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, функция может иметь несколько определений (clauses). Определённое определение выполняется, когда переданные функции аргументы соответствуют аргументам определения (pattern matching) и его условия (guards) вычисляются в true.

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

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

Теперь мы снова выполняем ту же функцию, начиная с первого определения. Учитывая, что второй аргумент, n, по-прежнему больше нуля, мы выводим сообщение и снова вызываем себя, теперь со вторым аргументом, установленным в 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

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.