那個很有名的英文程式問答網站

記得當我們昨天在一步步執行遞迴時，在加總前的最後一步是 (1 + (2 + (3 + 0))) 嗎？在遞迴的每一步想要回傳，但仍然有沒辦法處理的部份時，就會先把目前手上的東西，放到記憶體裡一個叫做 stack (堆棧) 的地方，等到知道怎麼解決時再拿回來算。而在我們範例的執行過程中，stack 的狀態有點像是這樣：

*1 (1 + 等第二行)
*2 (2 + 等第三行)
*3 (3 + 等第四行)
*4 0

一直到要第四行回傳了可運算的值，上面那些在等待的部份才會一個個清上去。只有四行當然沒什麼問題，但若在呼叫這個函式時，有人傳了上億個元素的串列進來，stack 就會被塞爆了，情況比較好就是跑很慢，情況差的時候，就會噴那個著名的 stack overflow 錯誤出來。所以你看一下那個同名的英文程式問答網站 logo，相當傳神的展示了這種情況。

尾呼叫最佳化 (tail call optimization)

想解決這個問題，要符合兩個條件，第一個條件就是該語言的 VM 要實作 tail call optimization，尾呼叫最佳化。聽起來很厲害，但是其實就是一條規則：

如果函式執行的最後一行，是另一個單純的函式呼叫時，那就直接把這個 stack 替換成新的函式呼叫。

試想有下面這樣一段程式碼：

def foo(x) do
  # 做些什麼事，產生 y
  bar(y) # 沒有計算跟其它有的沒的，就是個單純的函式呼叫
end

剛呼叫時，stack 長這樣：

*1 foo(x)

而算完中間的部份，運行到最後一行回傳時，stack 會被替換成這樣：

*1 bar(y)

既然 stack 完全沒有往下堆，也就不存在被塞爆的煩惱了。大多數的函數式編程語言都會在 VM 上實作 tail call optimization，elixir/erlang 當然也不例外。值得一提的是，之前的版本沒有硬性規定，但 JavaScript 從 ES6 開始，規範要實作 tail call optimization，且會在程式宣告嚴格模式的時候生效。

尾遞迴版本的 Math.sum

剛剛提到了解決問題的兩個條件。除了 VM 的實作之外，我們要調整一下程式碼，使其符合回傳時是一個單純的函式呼叫這條件。在遞迴裡用了尾呼叫，就稱為尾遞迴。實際的做法，就是把目前已求得的值當做另一個參數，往下傳：

def sum([], total), do: total
def sum([h | t], total), do: sum(t, h + total)

# 呼叫時
sum([1, 2, 3], 0)

我們新版的 sum 需要兩個參數，除了原先要加總的串列之外，多放一個 0 當做 total 的起始值 (其實就是我們之前遇到空串列時的那個回傳值)。接下來在遞迴的過程中，每一步我們都用首值跟 total 相加，再用剩下的串列，以及這個新加好的 total 當做參數，遞迴的呼叫自己。最後遇到空串列時，直接回傳 total。

再模擬一下我們的 stack，因為永遠只有一層，所以用箭號 => 來表示每個呼叫的歷程：

#1 sum([1,2,3], 0) => sum([2, 3], 1) => sum([3], 3) => sum([], 6) => 6

但是這個函式比較醜…

問題解決了，但是我們的函式從只要一個參數，變成需要兩個參數。呼叫時都要把對我們沒意義的起始值一起傳進去。在 elixir 裡要解決這個問題，有兩個方式：

方案 A: 繼續利用 pattern matching

我們可以用 pattern matching 來定義同名，不同參數個數的函式。像這樣：

def sum(x), do: sum(x, 0)

defp sum([], total), do: total
defp sum([h|t], total), do: sum(t, h + total)

這裡我們把接收兩個參數的 sum 改用 defp 來定義，這是 elixir 裡宣告私有函式 (private function) 的方式。只有在同一個模組裡的程式才能呼叫它。但這不是必須的，用原先的 def 也能正常運作。但這樣的目的是為了不對外界曝露兩個變數的呼叫方式，絕對不是單純只是為了展示語法所編造的例子。

方案 B: 參數預設值

如果你希望對外界同時提供一個參數及兩個參數的呼叫方式時，就可以使用參數預設值來解決這個問題。參數預設值的語法如下：

def foo(x \\ 1) do
  ## blah
end

在參數後方加上兩個反斜線 \\ ， 並在後面寫上預設值。所以我們的程式可以改成這樣：

def sum([], total), do: total
def sum([h|t], total \\ 0), do: sum(t, h + total)

試著執行看看，會發現雖然可以印出正確的值，但是 elixir 噴了個警告給我們：warning: definitions with multiple clauses and default values require a header. 這段是說因為我們的函式有多個相同參數個數的區塊 (clause)，所以要把預設值放在 header 裡。正確的寫法如下：

def sum(list, total \\ 0)
def sum([], total), do: total
def sum([h|t], total), do: sum(t, h + total)

所謂的 head ，就是沒有函式本體 do...end 或是 do: 的函式宣告。

重點回顧

• 遞迴的函式可能會造成 stack overflow
• 若 VM 實作了 tail call optimization，且函式呼叫回傳的那一步是一個單純的函式呼叫，不會在 stack 上疊東西
• 多放一個參數來實作尾遞迴版本的函式
• 可以用 pattern matching 或參數預設值來解決多一個參數的問題
• defp 用來宣告私有函式
• \\ 用來宣告參數預設值
• 有多個同參數個數的函式版本時，參數預設值要提出來，寫在最上方的 header 裡。

下一篇將討論 guards 及著名的 Pipe operator。

Happy hacking! 明天見。