9-递归

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

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

上面例子中，我们改变了array，以及辅助变量i的值。这在Elixir中是不可能的。 尽管如此，函数式语言却依赖于某种形式的循环—-递归：一个函数可以不断地被递归调用，直到某条件满足才停止。 考虑下面的例子：打印一个字符串若干次：

  1. defmodule Recursion do
  2.   def print_multiple_times(msg, n) when n <= 1 do
  3.     IO.puts msg
  4.   end
  6.   def print_multiple_times(msg, n) do
  7.     IO.puts msg
  8.     print_multiple_times(msg, n - 1)
  9.   end
  10. end
  12. Recursion.print_multiple_times("Hello!", 3)
  13. # Hello!
  14. # Hello!
  15. # Hello!

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

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

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

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

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

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

  1. defmodule Math do
  2.   def sum_list([head|tail], accumulator) do
  3.     sum_list(tail, head + accumulator)
  4.   end
  6.   def sum_list([], accumulator) do
  7.     accumulator
  8.   end
  9. end
  11. 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。

几次函数调用情况如下：

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

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

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

此处使用了递归来遍历列表元素，使它们加倍，然后返回新的列表。 这样以列表为参数，递归处理其每个元素的方式，称为“映射（map）”算法。

递归和列尾调用优化（tail call optimization）是Elixir中重要的部分，通常用来创建循环。 尽管如此，在Elixir中你很少会使用以上方式来递归地处理列表。

下一章要介绍的Enum模块为操作列表提供了诸多方便。 比如，下面例子：

  1. iex> Enum.reduce([1, 2, 3], 0, fn(x, acc) -> x + acc end)
  2. 6
  3. iex> Enum.map([1, 2, 3], fn(x) -> x * 2 end)
  4. [2, 4, 6]

或者，使用捕捉的语法：

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