Рекурсия

Циклы через рекурсию

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

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

В примере выше мы изменяем и массив, и переменную i. Изменение невозможно в Эликсире. Функциональные языки в противовес полагаются на рекурсию: функция вызывается рекурсивно, пока условие для остановки не будет достигнуто. Никакие данные в процессе не изменяются. Посмотрите на пример ниже, который печатает строку указанное количество раз:

defmodule Recursion do
  def print_multiple_times(msg, n) when n <= 1 do
    IO.puts msg
  end

  def print_multiple_times(msg, n) do
    IO.puts msg
    print_multiple_times(msg, n – 1)
  end
end

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

Аналогично конструкции case функция может иметь несколько вариантов вызова. Определённый вариант будет выполнен, когда переданные аргументы удовлетворяют образцу аргументов и его охранное условие возвращает true.

При вызове функции print_multiple_times/2 в примере выше, аргумент n равен 3.

Первый вариант имеет ограничение, которое говорит «используй это определение тогда и только тогда, когда n меньше или равно 1». Т. к. в начале этот вариант не подходит, используется следующее определение.

Второе определение подходит шаблону и не имеет ограничений, таким образом оно будет выполнено. При этом будет напечатано сообщение msg и будет вызвана эта же функция с n – 1 (2) в качестве второго аргумента.

Сообщение msg напечатано и функция print_multiple_times/2 вызывается снова, на этот раз со вторым аргументом 1. Т. к. n теперь равно 1, ограничение из первого определения вернёт true и выполнится соответствующий ему код. Сообщение msg будет напечатано и больше ничего не останется для выполнения.

Мы определили функцию print_multiple_times/2 так, что неважно, какое число будет передано в качестве второго аргумента, будет или выполнено первое определение (его можно назвать базовым случаем) или второе, которое приблизит нас на шаг к базовому случаю.

Алгоритмы редукции и словаря

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

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.

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

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

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 algorith).

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

Модуль 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.