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
```
這種使用列表做參數，每次削減一點列表的遞歸方式，稱為“遞減”算法，是函數式編程的核心。
<br/>
如果我們想給每個列表元素加倍呢？：
```
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）”算法。
<br/>
遞歸和列尾調用優化（tail call optimization）是Elixir中重要的部分，通常用來創建循環。
盡管如此，在Elixir中你很少會使用以上方式來遞歸地處理列表。
下一章要介紹的[Enum模塊](http://elixir-lang.org/docs/stable/elixir/Enum.html)為操作列表提供了諸多方便。
比如，下面例子：
```
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]
```
