[TOC] 當一個函數在其函數體內調用自身，則稱之為遞歸。最經典的例子便是計算斐波那契數列，即每個數均為前兩個數之和。 數列如下所示： ~~~ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, … ~~~ 下面的程序可用于生成該數列（示例 6.13?[fibonacci.go](https://github.com/Unknwon/the-way-to-go_ZH_CN/blob/master/eBook/examples/chapter_6/fibonacci.go)）： ~~~ package main import "fmt" func main() { result := 0 for i := 0; i <= 10; i++ { result = fibonacci(i) fmt.Printf("fibonacci(%d) is: %d\n", i, result) } } func fibonacci(n int) (res int) { if n <= 1 { res = 1 } else { res = fibonacci(n-1) + fibonacci(n-2) } return } ~~~ 輸出： ~~~ fibonacci(0) is: 1 fibonacci(1) is: 1 fibonacci(2) is: 2 fibonacci(3) is: 3 fibonacci(4) is: 5 fibonacci(5) is: 8 fibonacci(6) is: 13 fibonacci(7) is: 21 fibonacci(8) is: 34 fibonacci(9) is: 55 fibonacci(10) is: 89 ~~~ 許多問題都可以使用優雅的遞歸來解決，比如說著名的快速排序算法。 在使用遞歸函數時經常會遇到的一個重要問題就是棧溢出：一般出現在大量的遞歸調用導致的程序棧內存分配耗盡。這個問題可以通過一個名為[懶惰求值](https://zh.wikipedia.org/wiki/%E6%83%B0%E6%80%A7%E6%B1%82%E5%80%BC)的技術解決，在 Go 語言中，我們可以使用管道（channel）和 goroutine（詳見第 14.8 節）來實現。練習 14.12 也會通過這個方案來優化斐波那契數列的生成問題。 Go 語言中也可以使用相互調用的遞歸函數：多個函數之間相互調用形成閉環。因為 Go 語言編譯器的特殊性，這些函數的聲明順序可以是任意的。下面這個簡單的例子展示了函數 odd 和 even 之間的相互調用（示例 6.14?[mut_recurs.go](https://github.com/Unknwon/the-way-to-go_ZH_CN/blob/master/eBook/examples/chapter_6/mut_recurs.go)）： ~~~ package main import ( "fmt" ) func main() { fmt.Printf("%d is even: is %t\n", 16, even(16)) // 16 is even: is true fmt.Printf("%d is odd: is %t\n", 17, odd(17)) // 17 is odd: is true fmt.Printf("%d is odd: is %t\n", 18, odd(18)) // 18 is odd: is false } func even(nr int) bool { if nr == 0 { return true } return odd(RevSign(nr) - 1) } func odd(nr int) bool { if nr == 0 { return false } return even(RevSign(nr) - 1) } func RevSign(nr int) int { if nr < 0 { return -nr } return nr } ~~~ ### [](https://github.com/Unknwon/the-way-to-go_ZH_CN/blob/master/eBook/06.6.md#練習題)練習題 **練習 6.4** 重寫本節中生成斐波那契數列的程序并返回兩個命名返回值（詳見第 6.2 節），即數列中的位置和對應的值，例如 5 與 4，89 與 10。 **練習 6.5** 使用遞歸函數從 10 打印到 1。 **練習 6.6** 實現一個輸出前 30 個整數的階乘的程序。 n! 的階乘定義為：`n! = n * (n-1)!, 0! = 1`，因此它非常適合使用遞歸函數來實現。 然后，使用命名返回值來實現這個程序的第二個版本。 特別注意的是，使用 int 類型最多只能計算到 12 的階乘，因為一般情況下 int 類型的大小為 32 位，繼續計算會導致溢出錯誤。那么，如何才能解決這個問題呢？ 最好的解決方案就是使用 big 包（詳見第 9.4 節）。