當(dāng)一個(gè)函數(shù)在其函數(shù)體內(nèi)調(diào)用自身，則稱之為遞歸。最經(jīng)典的例子便是計(jì)算斐波那契數(shù)列，即前兩個(gè)數(shù)為1，從第三個(gè)數(shù)開始每個(gè)數(shù)均為前兩個(gè)數(shù)之和。
數(shù)列如下所示：
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …下面的程序可用于生成該數(shù)列（示例 6.13 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許多問題都可以使用優(yōu)雅的遞歸來解決，比如說著名的快速排序算法。
在使用遞歸函數(shù)時(shí)經(jīng)常會(huì)遇到的一個(gè)重要問題就是棧溢出：一般出現(xiàn)在大量的遞歸調(diào)用導(dǎo)致的程序棧內(nèi)存分配耗盡。這個(gè)問題可以通過一個(gè)名為懶惰求值的技術(shù)解決，在 Go 語言中，我們可以使用管道（channel）和 goroutine（詳見第 14.8 節(jié)）來實(shí)現(xiàn)。練習(xí) 14.12 也會(huì)通過這個(gè)方案來優(yōu)化斐波那契數(shù)列的生成問題。
Go 語言中也可以使用相互調(diào)用的遞歸函數(shù)：多個(gè)函數(shù)之間相互調(diào)用形成閉環(huán)。因?yàn)?Go 語言編譯器的特殊性，這些函數(shù)的聲明順序可以是任意的。下面這個(gè)簡單的例子展示了函數(shù) odd 和 even 之間的相互調(diào)用（示例 6.14 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
}練習(xí) 6.4
重寫本節(jié)中生成斐波那契數(shù)列的程序并返回兩個(gè)命名返回值（詳見第 6.2 節(jié)），即數(shù)列中的位置和對應(yīng)的值，例如 5 與 4，89 與 10。
練習(xí) 6.5
使用遞歸函數(shù)從 10 打印到 1。
練習(xí) 6.6
實(shí)現(xiàn)一個(gè)輸出前 30 個(gè)整數(shù)的階乘的程序。
n! 的階乘定義為：n! = n * (n-1)!, 0! = 1，因此它非常適合使用遞歸函數(shù)來實(shí)現(xiàn)。
然后，使用命名返回值來實(shí)現(xiàn)這個(gè)程序的第二個(gè)版本。
特別注意的是，使用 int 類型最多只能計(jì)算到 12 的階乘，因?yàn)橐话闱闆r下 int 類型的大小為 32 位，繼續(xù)計(jì)算會(huì)導(dǎo)致溢出錯(cuò)誤。那么，如何才能解決這個(gè)問題呢？
最好的解決方案就是使用 big 包（詳見第 9.4 節(jié)）。
掃碼關(guān)注鍍金池微信號(hào)
手機(jī)訂課，優(yōu)惠多多