递归 | Recursion

递归

循环递归

由于不变性，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 <= 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” 时才使用此定义。由于情况并非如此，Elixir 进入了下一个条款的定义。

第二个定义与模式相匹配，并没有防范，所以它会被执行。它首先打印我们的msg，然后调用自己作为第二个参数传递n - 1（2）。

我们msg被打印并print_multiple_times/2再次被调用，这次设置为第二个参数1。因为n现在被设置为1，我们的第一个定义中的守卫print_multiple_times/2评估为真，并且我们执行这个特定的定义。这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]

这里我们使用递归来遍历一个列表，每个元素加倍并返回一个新列表。获取列表并映射它的过程称为映射算法。

递归和尾部调用优化是 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]

让我们更深入地看看Enumerables，而当我们谈论它时，他们懒惰的对手Streams。