Elixir入门教程－递归

发表于   |   分类于 ，
  1. 用递归实现循环
  2. reduce 和 map 算法

用递归实现循环

由于不可修改的特性，Elixir里的循环（如任何其他函数式语言原因）和命令式语言的写法不同。例如，在命令式语言，如C里，循环的写法如下：

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

在上述例子里，我们修改数组和变量i。在Elixir里修改变量值是不可能的。相反，函数式语言依赖于递归：一个函数被递归地调用，直到一个条件符合了才停止递归动作继续进行。在这个过程里面，没有数据被修改。思考一下下面的例子，打印一个字符串任意次数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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的时候使用这个分支”。因为一开始的时候n等于3，这个条件不成立，则Elixir处理下一个分支定义。

第二个分支定义匹配这个模式并且没有卫语句，因此它将被执行。它首先打印我们的 msg 变量，然后传递 n - 1 （2）作为第二个入参并调用自己。

我们的 msg 变量被打印并且 print_multiple_times/2 被再次调用，这次第二个入参为1。因为n现在为1，print_multiple_times/2 的第一个分支定义的卫语句结果为true，那么我们执行这个特定的分支定义。msg被打印，并且没有其他需要执行的。

我们这样定义 print_multiple_times/2 ，不管传递的第二个参数是什么数值，它可能触发我们第一个分支（也就是基准条件），或者它出发我们第二个分支，它将确保我们离我们的基准条件更近一步。

reduce 和 map 算法

现在让我们看看我们如何利用递归的能力来对数字列表进行求和：

1
2
3
4
5
6
7
8
9
10
11
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]，这个情况一直到列表为空为止。参见如下演示：

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

当列表为空，它将匹配最后一个分支，然后返回最后结果为6。

将列表分解为一个值的过程称为归约算法，是函数编程的核心。

如果我们想将我们列表的所有元素值都翻倍，我们该如何做呢？

1
2
3
4
5
6
7
8
9
defmodule Math do
  def double_each([head | tail]) do
    [head * 2 | double_each(tail)]
  end
  def double_each([]) do
    []
  end
end
1
iex math.exs
1
iex> Math.double_each([1, 2, 3]) #=> [2, 4, 6]

在这里我们用递归遍历列表，将其每个元素值翻倍，并且返回一个新的列表。获取列表并在其上映射的过程称为映射算法。

递归和尾调用是Elixir里重要的部分并且也是通常用来创建循环的方法。然后，当你在Elixir里编程，你将几乎很少像上面例子那样使用递归来操作列表。

我们将在下一章看到的 Enum模块 已经提供了许多操作列表的便捷方式。例如，上述例子可以按如下方式来写：

1
2
3
4
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]

或者使用捕获语法：

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

让我们更深入地了解可枚举的数据类型：Enumerable，以及它的懒惰对应数据类型：Steam。

原文链接： http://elixir-lang.org/getting-started/recursion.html