递归函数
当一个函数在其函数体内调用自身,则称之为递归。最经典的例子便是计算斐波那契数列,即前两个数为1,从第三个数开始每个数均为前两个数之和。
数列如下所示:
下面的程序可用于生成该数列(示例 6.13 fibonacci.go):
输出:
许多问题都可以使用优雅的递归来解决,比如说著名的快速排序算法。
在使用递归函数时经常会遇到的一个重要问题就是栈溢出:一般出现在大量的递归调用导致的程序栈内存分配耗尽。这个问题可以通过一个名为懒惰求值的技术解决,在 Go 语言中,我们可以使用管道(channel)和 goroutine(详见第 14.8 节)来实现。练习 14.12 也会通过这个方案来优化斐波那契数列的生成问题。
Go 语言中也可以使用相互调用的递归函数:多个函数之间相互调用形成闭环。因为 Go 语言编译器的特殊性,这些函数的声明顺序可以是任意的。下面这个简单的例子展示了函数 odd 和 even 之间的相互调用(示例 6.14 mut_recurs.go):
练习题
练习 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 节)。
链接
Last updated