9-递归

因为在Elixir中（或所有函数式语言中），数据有不变性（immutability），因此在写循环时与传统的命令式（imperative）语言有所不同。例如某命令式语言的循环可以这么写：

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

上面例子中，我们改变了array，以及辅助变量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!

一个函数可以有许多子句（上面看起来定义了两个函数，但卫兵条件不同，可以看作同一个函数的两个子句）。当参数匹配该子句的模式，且该子句的卫兵表达式返回true，才会执行该子句内容。上面例子中，当print_multiple_times/2第一次调用时，n的值是3。

第一个子句有卫兵表达式要求n必须小于等于1。因为不满足此条件，代码找该函数的下一条子句。

参数匹配第二个子句，且该子句也没有卫兵表达式，因此得以执行。首先打印msg，然后调用自身并传递第二个参数n-1(=2)。这样msg又被打印一次，之后调用自身并传递参数n-1(=1)。

这个时候，n满足第一个函数子句条件。遂执行该子句，打印msg，然后就此结束。

我们称例子中第一个函数子句这种子句为“基本情形”。基本情形总是最后被执行，因为起初通常都不匹配执行条件，程序而转去执行其它子句。但是，每执行一次其它子句，条件都向这基本情形靠拢一点，直到最终回到基本情形处执行代码。

下面我们使用递归的威力来计算列表元素求和：

defmodule Math do
  def sum_list([head|tail], accumulator) do
    sum_list(tail, head + accumulator)
  end

  def sum_list([], accumulator) do
    accumulator
  end
end

Math.sum_list([1, 2, 3], 0) #=> 6

我们首先用列表[1,2,3]和初值0作为参数调用函数，程序将逐个匹配各子句的条件，执行第一个符合要求的子句。于是，参数首先满足例子中定义的第一个子句。参数匹配使得head = 1，tail = [2,3]，accumulator = 0。

然后执行该字据内容，把head + accumulator作为第二个参数，连带去掉了head的列表做第一个参数，再次调用函数本身。如此循环，每次都把新传入的列表的head加到accumulator上，传递去掉了head的列表。最终传递的列表为空，符合第二个子句的条件，执行该子句，返回accumulator的值6。

几次函数调用情况如下：

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

这种使用列表做参数，每次削减一点列表的递归方式，称为“递减”算法，是函数式编程的核心。
如果我们想给每个列表元素加倍呢？：

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）”算法。

递归和列尾调用优化（tail call optimization）是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]