> For the complete documentation index, see [llms.txt](https://ryanyang.gitbook.io/the-way-to-go-zh-cn/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ryanyang.gitbook.io/the-way-to-go-zh-cn/di-er-bu-fen-yu-yan-de-he-xin-jie-gou-yu-ji-shu/06.0/06.6.md).

# 递归函数

当一个函数在其函数体内调用自身，则称之为递归。最经典的例子便是计算斐波那契数列，即前两个数为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](https://github.com/yangchuansheng/the-way-to-go_ZH_CN/tree/f30ab7d8c58f85840a0afb548024b93642b518d5/eBook/examples/chapter_6/fibonacci.go)）：

```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/惰性求值)的技术解决，在 Go 语言中，我们可以使用管道（channel）和 goroutine（详见第 14.8 节）来实现。练习 14.12 也会通过这个方案来优化斐波那契数列的生成问题。

Go 语言中也可以使用相互调用的递归函数：多个函数之间相互调用形成闭环。因为 Go 语言编译器的特殊性，这些函数的声明顺序可以是任意的。下面这个简单的例子展示了函数 odd 和 even 之间的相互调用（示例 6.14 [mut\_recurs.go](https://github.com/yangchuansheng/the-way-to-go_ZH_CN/tree/f30ab7d8c58f85840a0afb548024b93642b518d5/eBook/examples/chapter_6/mut_recurs.go)）：

```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
}
```

### 练习题

**练习 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 节）。

## 链接

* [目录](https://github.com/yangchuansheng/the-way-to-go_ZH_CN/tree/f30ab7d8c58f85840a0afb548024b93642b518d5/eBook/directory.md)
* 上一节：[内置函数](/the-way-to-go-zh-cn/di-er-bu-fen-yu-yan-de-he-xin-jie-gou-yu-ji-shu/06.0/06.5.md)
* 下一节：[将函数作为参数](/the-way-to-go-zh-cn/di-er-bu-fen-yu-yan-de-he-xin-jie-gou-yu-ji-shu/06.0/06.7.md)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ryanyang.gitbook.io/the-way-to-go-zh-cn/di-er-bu-fen-yu-yan-de-he-xin-jie-gou-yu-ji-shu/06.0/06.6.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.