查看源代码 递归

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,一个函数可能有多个子句。当传递给函数的参数与子句的参数模式匹配,并且其守卫表达式计算结果为 true 时,执行特定子句。

当上面的例子中最初调用 print_multiple_times/2 时,参数 n 等于 3

第一个子句有一个守卫表达式,它说“当且仅当 n 大于 0 时,使用此定义”。由于情况确实如此,它打印 msg,然后递归调用自身,将 n - 1 (2) 作为第二个参数传递。

现在我们再次执行同一个函数,从第一个子句开始。鉴于第二个参数 n 仍然大于 0,我们打印消息并再次调用自身,现在将第二个参数设置为 1。然后我们最后一次打印消息并调用 print_multiple_times("Hello!", 0),再次从顶部开始。

当第二个参数为零时,守卫表达式 n > 0 计算结果为假,第一个函数子句将不会执行。然后,Elixir 继续尝试下一个函数子句,该子句明确匹配 n0 的情况。这个子句,也被称为终止子句,通过将其分配给 _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

我们使用列表 [1, 2, 3] 和初始值 0 作为参数调用 sum_list。我们会尝试每个子句,直到找到一个根据模式匹配规则匹配的子句。在这种情况下,列表 [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