Go 語言中的遞迴和尾呼叫操作
曾幾何時，我看過一段關於 Go 遞迴函式的簡單例子，作者用了極快的速度簡單的陳述了 Go 這門語言中並沒有優化遞迴這一操作，即使是在尾呼叫（tail calls）非常明顯的時間。我當時並不理解什麼是尾呼叫（tail calls），我非常想知道這位作者提到的 Go 語言沒有優化遞迴操作的原因是什麼，因為我從來不知道原來遞迴操作還可以被優化。
有些人不太理解什麼是遞迴操作，其實可以用一種簡單的說法來解釋，就是函式自己呼叫自己本身。 那為什麼我們會需要寫一個函式來呼叫自己本身呢？舉個例子，遞迴演算法在使用棧（stack，先進後出）來執行資料操作的時候是非常方便的，它比迴圈操作更快，並且程式碼的簡潔性好。
執行數學操作時，一個典型的遞迴場景是：當前的計算結果是下一步計算的輸入。對於所有的遞迴操作，你必須設定一個錨點 (anchor) 觸發遞迴函式的結束，並返回結果。如果不這樣操作，那麼遞迴函式將會進入無窮無盡的迴圈當中，最終引發記憶體溢位。
為什麼你的程式會引發記憶體溢位？ 在傳統的 C 語言程式中，棧記憶體是用來處理所有函式呼叫的地方，這是因為棧是一種預分配的記憶體，並且速度非常快。例如下圖所示：
上面這個圖描述了一個典型的棧記憶體例子，並且它也許和我們所寫的所有程式類似。你可以從圖中看到，棧記憶體會隨著函式呼叫而增加，每一次我們從一個函式中呼叫另一個函式、變數、暫存器和資料的時候，總是會把這些引數地址或者變數名壓入棧內，從而使得它記憶體增加。
在 C 程式中，每個執行緒自身都有一定的棧記憶體空間，根據結構的不同，棧記憶體的大小當然也不一樣，大概從 1M 到 8M 不等。當然，你也可以調節預設值小大。如果你寫的程式會產生大量的執行緒，那麼你將會迅速的用完那些你不可能會用掉的記憶體。
在 Go 程式中，每個 Goroutine 都會分配棧記憶體，但是 Go 更加智慧一些：剛開始會分配 4K，之後按需增長。Go 語言能夠動態的增加棧記憶體的概念來自於 split stacks( 棧分割 )。關於更多 split stacks 的內容請移步：
http://gcc.gnu.org/wiki/SplitStacks
你同時還可以參考下面 Go 語言中 runtime 包裡的棧實現程式碼：
- http://golang.org/src/pkg/runtime/stack.h
- http://golang.org/src/pkg/runtime/stack.c
當你要使用遞迴的時候，你需要意識到棧記憶體是一直增加的，直到遇到你設定好的 anchor 時，它的記憶體才開始下降。當我們說 Go 並沒有優化遞迴操作時，我們需要承認一個事實，Go 並沒有嘗試著去優化棧記憶體無限增加這一操作。這個時候 tail calls 就登場了。
在介紹 tail calls 是如何優化遞迴函式之前，讓我們來看一個簡單的遞迴函式：
func Recursive(number int) int {
if number == 1 {
return number
}
return number + Recursive(number-1)
}
func main() {
answer := Recursive(4)
fmt.Printf("Recursive: %d\n", answer)
}
上面的這個遞迴函式需要傳入一個整數作為引數，並 return 回一個整數。如果傳入函式值是 1，那麼函式將會立馬返回。這個 if 函式包含了錨點，並採用棧來完成執行任務。
如果傳入的變數並不是 1，那麼遞迴函式將開始工作。遞迴函式將引數值減去 1，然後使用減掉後的引數作為下一次遞迴呼叫的引數。棧記憶體隨著每一次的函式呼叫增加，直到達到錨點，所有的遞迴呼叫開始返回一直到主函式。
讓我們看看上圖中所有的函式呼叫和返回值是怎麼操作的：
- 該流程圖，從左下角開始，至下往上的遞迴操作，該流程展現了詳細的呼叫鏈。
- 主函式中呼叫遞迴函式傳入引數 4，接著遞迴函式呼叫自身傳入引數 3。這樣反覆呼叫，直到引數值 1 傳入遞迴函式。
- 遞迴函式在 return 前呼叫自己三次，當到達錨點的時候有 3 個擴充套件棧楨（extended stack frames）對應每一個呼叫操作。
- 接著，遞迴開始展開，真正的工作開始進行。從圖中可知，右邊從上到下就是展開操作。
- 每一個 return 操作通過獲取引數並將其新增到函式呼叫的返回值來執行每個返回操作。
- 最後的 return 操作執行後我們得到了最終的答案 10。
遞迴函式執行這些步驟非常迅速，因此這就是遞迴的好處，我們不需要任何迭代或者計數進行迴圈。棧將當前的結果儲存起來返回給之前的函式。當然，我們唯一需要的擔心的是我們需要消耗多少記憶體。
什麼是 tail calls ？它是如何優化遞迴函式的？ 接下來將建立一個帶有 tail calls 的遞迴函式，瞭解它是如何解決遞迴函式消耗大量棧記憶體問題的。
下面是同樣的遞迴函式，但它是通過 tail call 實現的：
func TailRecursive(number int, product int) int {
product = product + number
if number == 1 {
return product
}
return TailRecursive(number-1, product)
}
func main() {
answer := TailRecursive(4, 0)
fmt.Printf("Recursive: %d\n", answer)
}
你能發現他們之間的不同嗎？它與我們如何使用堆疊和計算結果有關。在這個實現中，錨點竟然返回了最終結果！除了最終值，我們不再需要任何棧的返回值。
一些編譯器能夠看到這種細微差別，並更改生成的底層程式集，以便對所有遞迴呼叫使用一個棧框架。Go 編譯器還無法檢測到這種細微差別。為了證明讓我們來看看 Go 編譯器為這兩個函式生成的彙編程式碼。
為了產生彙編程式碼，讀書可在終端執行下面的命令：
go tool 6g -S ./main.go > assembly.asm
根據你的機器架構，一般有三種編譯器。
- 6g: AMD64 架構： 無論處理器是由英特爾還是 AMD 構建，這都適用於現代 64 位處理器。AMD 開發了 x86 架構的 64 位擴充套件。
- 8g: x86 架構：基於 8086 架構，適用於 32 位處理器。
- 5g: ARM 架構：適用於基於 RISC 的處理器，代表精簡指令集計算。
需要學習更多關於架構的知識或者其他 Go 工具命令的可移步：http://golang.org/cmd/gc/
我下面同時列出了 Go 程式碼和彙編程式碼。希望其中的一項能幫助到你理解。
為了讓處理器能夠操作資料，類似於加法運算或者數值對比，資料必須存在暫存器中。你可以想一想暫存器是如何處理變數的。 當你在看下面彙編程式碼的時候，你會了解到 AX 和 BX 是主要的暫存器，且它們經常被使用到。SP 暫存器是棧指標，FP 暫存器是幀指標，它也與棧有關。
那麼，讓我看看下面的程式碼：
07 func Recursive(number int) int {
08
09if number == 1 {
10
11return number
12}
13
14return number + Recursive(number-1)
15 }
— prog list "Recursive" —
0000 (./main.go:7) TEXT Recursive+0(SB),$16-16
0001 (./main.go:7) MOVQ number+0(FP),AX
0002 (./main.go:7) LOCALS ,$0
0003 (./main.go:7) TYPE number+0(FP){int},$8
0004 (./main.go:7) TYPE ~anon1+8(FP){int},$8
0005 (./main.go:9) CMPQ AX,$1
0006 (./main.go:9) JNE ,9
0007 (./main.go:11) MOVQ AX,~anon1+8(FP)
0008 (./main.go:11) RET ,
0009 (./main.go:14) MOVQ AX,BX
0010 (./main.go:14) DECQ ,BX
0011 (./main.go:14) MOVQ BX,(SP)
0012 (./main.go:14) CALL ,Recursive+0(SB)
0013 (./main.go:14) MOVQ 8(SP),AX
0014 (./main.go:14) MOVQ number+0(FP),BX
0015 (./main.go:14) ADDQ AX,BX
0016 (./main.go:14) MOVQ BX,~anon1+8(FP)
0017 (./main.go:14) RET ,
如果我們跟隨彙編程式碼，你會發現所有地方都有棧的身影：
- 0001: AX 暫存器中數值變數的值來自於棧
- 0005-0006: 數值變數和 1 進行對比，如果他們不相等，那麼就 jump 到 Go 程式碼的第 14 行
- 0007-0008: 到達錨點的時候，函式執行 return 操作，並把引數變數拷貝到棧中
- 0009-0010: 將引數變數減去 1
- 0011-0012: 將引數變數 push 到棧中並開始執行遞迴函式
- 0013-0015: 函式返回。返回值從棧中 pop 出來，傳入到 AX 暫存器中。同時，引數值從棧楨中傳入到 BX 暫存器，將他們相加
- 0016-0017: 相加後的結果拷貝到棧上，函式返回
彙編程式碼顯示的是我們正在進行的遞迴呼叫，並且值正按預期從棧中 push 和 pop。棧記憶體在增加，同時也一直在釋放。
現在，讓我們為包含 tail call 的遞迴函式生成彙編程式碼，看看 Go 編譯器是否優化了什麼。
17 func TailRecursive(number int, product int) int {
18
19product = product + number
20
21if number == 1 {
22
23return product
24}
25
26return TailRecursive(number-1, product)
27 }
— prog list "TailRecursive" —
0018 (./main.go:17) TEXT TailRecursive+0(SB),$24-24
0019 (./main.go:17) MOVQ number+0(FP),CX
0020 (./main.go:17) LOCALS ,$0
0021 (./main.go:17) TYPE number+0(FP){int},$8
0022 (./main.go:17) TYPE product+8(FP){int},$8
0023 (./main.go:17) TYPE ~anon2+16(FP){int},$8
0024 (./main.go:19) MOVQ product+8(FP),AX
0025 (./main.go:19) ADDQ CX,AX
0026 (./main.go:21) CMPQ CX,$1
0027 (./main.go:21) JNE ,30
0028 (./main.go:23) MOVQ AX,~anon2+16(FP)
0029 (./main.go:23) RET ,
0030 (./main.go:26) MOVQ CX,BX
0031 (./main.go:26) DECQ ,BX
0032 (./main.go:26) MOVQ BX,(SP)
0033 (./main.go:26) MOVQ AX,8(SP)
0034 (./main.go:26) CALL ,TailRecursive+0(SB)
0035 (./main.go:26) MOVQ 16(SP),BX
0036 (./main.go:26) MOVQ BX,~anon2+16(FP)
0037 (./main.go:26) RET ,
包含 tail calls 的函式產生了更多的彙編程式碼。但是，結果卻非常相似。事實上，從效能的角度來看，我們已經讓事情變得更糟了。
Go 沒有針對我們實施的 tail calls 進行任何優化。 我們仍然進行了和之前例子一樣相同的棧操作和遞迴呼叫。所以我猜 Go 目前沒有針對遞迴進行優化。 這並不意味著我們不應該使用遞迴，我們只要知道 Go 語言中有這種特性即可。
如果你有一個問題通過遞迴演算法可以完美的解決，但是又害怕浪費記憶體，那你可以考慮使用 channel 操作。不過，這項操作某種意義上來說會慢很多，但它確實能解決你的擔憂。以下是使用通道實現遞迴函式的方法：
func RecursiveChannel(number int, product int, result chan int) {
product = product + number
if number == 1 {
result <- product
return
}
Go RecursiveChannel(number-1, product, result)
}
func main() {
result := make(chan int)
RecursiveChannel(4, 0, result)
answer := <-result
fmt.Printf("Recursive: %d\n", answer)
}
它同樣採用 tail calls 實現。一旦 anchor 被擊中，最終答案就會產生，並將答案放入頻道。它並不是進行遞迴呼叫，而是生成一個 Goroutine，它提供了我們在 tail calls 示例中推送到棧的相同狀態。
唯一的區別是我們將一個無緩衝的 channel 傳遞給 Goroutine。只有錨點才能將資料寫入通道 , 且它並不會產生其他 Goruntine。
在 main 函式中，建立了一個無緩衝的通道，並使用初始引數和通道呼叫 RecursiveChannel 函式。該函式立即返回，但 main 不會終止，這是因為它等待資料寫入通道。一旦錨點被擊中並將答案寫入通道，main 函式喚醒結果並將其列印到螢幕上。在大多數情況下，main 將在 Goroutine 終止之前喚醒。
遞迴是編寫 Go 程式時可以使用的另一種工具。目前，Go 編譯器不會優化尾呼叫的程式碼，但是，Go 的未來版本沒有什麼理由不優化這個問題。如果程式執行時，記憶體大小問題是你考慮的一個因素，那麼你通過 channel 去模擬遞迴的操作未嘗不可。