当一个函数在其函数体内调用自身，则称之为递归。最经典的例子便是计算斐波那契数列，即前两个数为 1，从第三个数开始每个数均为前两个数之和。

数列如下所示：

  1. 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）：

  1. package main
  3. import "fmt"
  5. func main() {
  6.     result := 0
  7.     for i := 0; i <= 10; i++ {
  8.         result = fibonacci(i)
  9.         fmt.Printf("fibonacci(%d) is: %d\n", i, result)
  10.     }
  11. }
  13. func fibonacci(n int) (res int) {
  14.     if n <= 1 {
  15.         res = 1
  16.     } else {
  17.         res = fibonacci(n-1) + fibonacci(n-2)
  18.     }
  19.     return
  20. }

输出：

  1. fibonacci(0) is: 1
  2. fibonacci(1) is: 1
  3. fibonacci(2) is: 2
  4. fibonacci(3) is: 3
  5. fibonacci(4) is: 5
  6. fibonacci(5) is: 8
  7. fibonacci(6) is: 13
  8. fibonacci(7) is: 21
  9. fibonacci(8) is: 34
  10. fibonacci(9) is: 55
  11. fibonacci(10) is: 89

许多问题都可以使用优雅的递归来解决，比如说著名的快速排序算法。

在使用递归函数时经常会遇到的一个重要问题就是栈溢出：一般出现在大量的递归调用导致的程序栈内存分配耗尽。这个问题可以通过一个名为懒惰求值的技术解决，在 Go 语言中，我们可以使用管道（channel）和 goroutine（详见第 14.8 节）来实现。练习 14.12 也会通过这个方案来优化斐波那契数列的生成问题。

Go 语言中也可以使用相互调用的递归函数：多个函数之间相互调用形成闭环。因为 Go 语言编译器的特殊性，这些函数的声明顺序可以是任意的。下面这个简单的例子展示了函数 odd 和 even 之间的相互调用（示例 6.14 mut_recurs.go）：

  1. package main
  3. import (
  4.     "fmt"
  5. )
  7. func main() {
  8.     fmt.Printf("%d is even: is %t\n", 16, even(16)) // 16 is even: is true
  9.     fmt.Printf("%d is odd: is %t\n", 17, odd(17))
  10.     // 17 is odd: is true
  11.     fmt.Printf("%d is odd: is %t\n", 18, odd(18))
  12.     // 18 is odd: is false
  13. }
  15. func even(nr int) bool {
  16.     if nr == 0 {
  17.         return true
  18.     }
  19.     return odd(RevSign(nr) - 1)
  20. }
  22. func odd(nr int) bool {
  23.     if nr == 0 {
  24.         return false
  25.     }
  26.     return even(RevSign(nr) - 1)
  27. }
  29. func RevSign(nr int) int {
  30.     if nr < 0 {
  31.         return -nr
  32.     }
  33.     return nr
  34. }

练习题

练习 6.4

重写本节中生成斐波那契数列的程序并返回两个命名返回值（详见第 6.2 节），即数列中的位置和对应的值，例如 4 与 5，89 与 10。

练习 6.5

使用递归函数从 10 打印到 1。

练习 6.6

实现一个输出前 30 个整数的阶乘的程序。

n! 的阶乘定义为：n! = n * (n-1)!, 0! = 1，因此它非常适合使用递归函数来实现。

然后，使用命名返回值来实现这个程序的第二个版本。

特别注意的是，使用 int 类型最多只能计算到 12 的阶乘，因为一般情况下 int 类型的大小为 32 位，继续计算会导致溢出错误。那么，如何才能解决这个问题呢？

最好的解决方案就是使用 big 包（详见第 9.4 节）。