本篇中我们会讨论递归。这是所有程序员或早或晚都会遇到的话题，也不完全是函数式编程范式的专属。任何语言，只要允许函数自己调用自己，本质上都是递归。对于大多数人，这不是什么难以理解的概念。在Haskell这样的函数式语言中，递归占据了中心为止。
本篇将聚焦理解递归是怎样工作的，性能有什么影响，以及Go中的限制。我们还会看看使用函数作为一等公民来构造递归。
什么是递归？
简单来说，递归就是一个函数调用自己的过程。实践中，下面的函数就是一个递归的例子：
func recursive() {
recursive()
}在这个例子中，如果用户调用recursive函数，它唯一会做的便是无穷无尽的调用自己。当然，这是个无限循环，没有实际的用处。为了让递归函数有用，我们需要扩展一下递归函数的定义，增加两条规则：
- 函数必须有一个条件来判断是否调用自己
- 函数必须有一个条件来判断返回什么，而不是调用自己
第一个条件描述的是给定函数X，在X内部的某处会调用其自身。第二个条件说的是存在这么一种情况，函数不需要调用自己就可以直接返回结果。第二种场景也称为base case。
为了理解这些概念，让我们来实现一个经典的数学操作，阶乘。阶乘函数接收一个整数输入，N，将从N到1所有的数字相乘，比如：
Fact(5) = 5 * 4 * 3 * 2 * 1为了理解这为什么是递归函数，可以看到，调用Fact(5)其实是用5乘以Fact(4)的结果。如果展开来的话，就是下面这样：
Fact(5) = 5 * Fact(4) = 5 * 24 = 120
Fact(4) = 4 * Fact(3) = 4 * 6 = 24
Fact(3) = 3 * Fact(2) = 3 * 2 = 6
Fact(2) = 2 * Fact(1) = 2 * 1 = 2
Fact(1) = 1 * Fact(0) = 1 * 1
Fact(0) = 1例子中，0的阶乘结果是1，这被定义为我们的base case，如果输入参数是0，则直接返回1。对于其它的输入，我们就将输入参数与input-1的阶乘结果相乘。
如果用Go代码实现，则像下面这样：
func main() {
fmt.Println(Fact(5))
}
func Fact(input int) int {
if input == 0 {
return 1
}
return input * Fact(input-1)
}
可以这样来思考，每次调用Fact函数的时候，都会向栈中压入一个函数。当所有的函数都压入了栈，然后便自顶向下求值，每一层都会使用上一层的结果来求值。
用栈的方式思考递归有助于理解本篇的例子和递归的陷阱。但在此之前，让我们看一个递归比循环更好用的情况，理解为什么函数式语言一般更偏好递归。
为什么函数式语言偏好递归？
在讨论何时在Go中使用递归函数之前，让我们先回答一个问题，为什么函数式语言更倾向于使用递归而非循环。最好的答案是，递归方法天生就比循环方法更加的纯粹。尽管每个用递归表达的函数都可以表达为循环，但是循环需要管理比递归更多的状态。
如果我们用循环的方式重写简单的阶乘函数，是这样的：
func factorial(n int) int {
result := 1
for i := 1; i <= n; i++ {
result = result * i
}
return result
}
在这个阶乘实现中，我们在for的每个循环中都会改变result的值。尽管这个变化不会逃逸出函数本身，但是这总还是一个状态变化。同时，递归的例子则永远不会改变状态，它是通过返回一个新的值来实现的：
return input * Fact(input-1)作为一个通用的规则，递归让我们通过状态复制来创建新函数，对副本做出改变，返回结果，而不在递归调用中直接改变值。这意味着每个对于程序状态的改动都被限制在了栈帧里面。
Go中的递归状态变化
在Go和其它的非纯语言中，还是有可能在递归函数调用中改变状态的。在这种语言中，递归不保证状态的不可变性，但确实更容易写出不可变的实现。
什么时候使用递归函数？
为了理解何时使用递归函数，我们必须先说清楚循环和递归函数之间的主要权衡。但在此之前，我们必须要说任何可以循环实现的东西都可以通过递归来实现。因此，每个包含for循环的语句，在Go中都可以被等价替换为递归式的函数调用。
然而我们未必总是想这么做。递归函数的缺点在于更多的时间和空间需求。多次调用一个函数就会创建多个栈帧，而栈帧又消耗着程序的工作内存。一般来说，每一帧都会包含下面的一帧中的数据的副本（递归函数的情况），也就是说每个函数都使用着和前面一样多的内存。而且这些栈帧又是同时存活的，递归调用不会弹出前面的栈帧，直到整个递归调用结束。因此在图7.1中看到，所有的栈帧是一层层叠加上去的，从上往下进行求值（后进先出）。如果用循环来写同样的函数，调用栈上就只有一个函数。
递归函数的另一个缺点是它执行起来要比循环的版本更慢，因为在编程语言中，函数调用是一种代价很大的操作。看调用栈的解释也能略知一二。每次函数调用都要把内存数据复制到一个新地方，执行核心算法，然后再复制回来执行下一个递归调用。
那么我们为什么还要使用递归函数呢？尽管上述限制都很重要，可我们更关心代码的可读性与可维护性。一旦掌握了递归，不仅代码写起来更容易，也更容易理解。涉及图或树遍历的算法很容易走向递归，因为这些数据结构本身就是递归的。本系列的主题之一便是性能和便捷性之间的权衡。
多提一句，在Haskell这种语言中，递归函数的语法要比Go中的简单，尤其是结合着模式匹配的概念时。我们快速看一眼Haskell中的阶乘实现，供参考：
factorial :: Integral -> Integral
factorial 0 = 1
factorial n = n * factorial (n-1)以上便是阶乘函数的完整实现。看起来更像是问题的数学描述，也让递归方案写起来更加吸引人。此外，Haskell还有编译器层面的递归函数优化机制。本篇后面我们会看到这种优化方案之一，尾递归优化。
遍历树结构
为了展示前面的假设，有的代码用递归的方式比循环的方式更容易实现，我们来看看遍历树结构的例子。树是一种递归的数据结构，引导大家走向了递归的算法实现。为了简便起见，假定我们有个保存着整数数据的树，具体的整数值不重要。我们构建出来的树像下面这样：
这里每个节点上的值不重要，我们要对所有节点中的数字求和。用文字描述的话，就是得到每个节点的值，然后看这个节点有没有子节点，如果有就把子节点的值也加入总和中。接下来，对于所有的子节点，再看它们是否有子节点，如果有，再将其子节点的值加入总和中，直到穷尽所有节点。
让我们创建一个数据结构来表示树结构。类型声明很明白：节点包含一个值，每个节点有一个指针指向左节点，一个指向右节点。子节点可有可无。
type node struct {
value int
left *node
right *node
}
有了这个结构体，我们再构建一个实际的树结构，用于示例函数中。我们可以在包层面上的var代码块中模拟图7.2的树结构：
var (
ExampleTree = &node{
value: 1,
left: &node{
value: 2,
left: &node{
value: 3,
},
right: &node{
value: 4,
},
},
right: &node{
value: 5,
},
}
)
在深入递归方案之前，我们先来试着使用for循环来遍历。
使用for循环遍历树结构
在动手之前我们先要引入一些额外的数据结构。我们要用到的数据结构是Queue。对于每个我们要访问的节点，我们将节点的值加入总和中。对于每个节点的子节点，我们将其加入Queue中，依此类推，直到清空Queue。起开始，我们将根节点加入Queue中开始整个流程。
有点要声明，写作本文的时候Go尚且没有提供开箱即用的队列实现。不过Go提供了一种带有缓冲的channel，提供与队列类似的行为，可以为我们所用。这种类似队列的特性主要包括：
- 可以将一个元素推入队列中
- 可以按照LIFO的模式从队列中移除一个元素
你可以使用切片来达成这个效果，不过还是存在切片管理的开销，不是性能最好的方案。真正的队列可以提供常量时间复杂度的添加和删除操作。为此，带有缓冲的channel可能效果更好，不过对此深入的探讨超出了本系列的范畴。还有一个前提假设是我们提前知道队列的尺寸。
真实场景中这是不可能的，你可以尽可能估算一个队列的长度传递给channel，但是很容易出问题。不过为了聚焦眼前的问题，我们暂且不管这些，接受上述前提假设。接下来看看如何通过迭代的方式获取所有节点的总和：
func sumIterative(root *node) int {
queue := make(chan *node, 10)
queue <- root
var sum int
for {
select {
case node := <-queue:
sum += node.value
if node.left != nil {
queue <- node.left
}
if node.right != nil {
queue <- node.right
}
default:
return sum
}
}
}
这个例子稍稍复杂了一些，因为我们需要用channel来模拟队列的行为。不过，核心算法是一样的，如果你使用真正的queue来实现的话，就不需要这里的select代码块了。
接下来我们看看如何用递归的方法解决问题。
递归式地遍历树结构
当我们用递归的思路来考察问题，它就变得清晰和易于实现了。
参考阶乘的例子，我们不断向栈中添加函数调用， 直至遇到base case，直接返回值而无需调用自己。此处的base case是空节点（nil指针）。这样的节点会返回一个0，不需要求和。对于其它的节点，我们返回其与子节点值的总和。如果用栈的形式可视化，那就是自底向上添加栈帧，但是从上往下求值，在这个过程中把值求出来：
func sumRecursive(node *node) int {
if node == nil {
return 0
}
return node.value + sumRecursive(node.left) +
sumRecursive(node.right)
}
这段递归代码是一种高效解决问题的方法，比循环的写法更容易读懂，也更贴近我们的意图。那么这个递归的方案和至今涉及的函数式方案有什么关联呢？
在函数式编程语言中，你要告诉电脑做什么，而不是如何做。当你手写循环的时候，你就陷入了如何做，而非做什么。此外，递归的做法也不会改变任何状态，更接近函数式编程世界中的理想函数。
函数式语言和循环
尽管函数式语言更加偏好递归，但也提供了手动创建循环的方法。它们还为递归函数提供了编译器层面的优化，使之在解决问题的时候更有吸引力。
把递归和函数作为一等公民
本篇截至目前的内容可以应用于任何带有函数调用的语言，即便是面向对象语言。本节我们将看一下如何利用函数式或者多范式语言的概念来让递归更容易编写和管理。
我认为最有用的功能之一便是将递归与闭包结合起来。作为例子，假设我们要递归处理一个数据结构，还需要跟踪一些状态。相比于在包的层面跟踪状态，或者使用复杂的递归函数在函数中跟踪状态，我们可以创建一个非递归的外层函数，其中使用一个递归的内层函数。光这样说可能不容易理解，还是通过具体的例子来展示。
还是使用和前面一样的树结构，我们来写一个函数，寻找树结构中值最大的节点。为此我们需要跟踪迄今为止的最大值。方法之一是使用递归函数之外的全局变量来跟踪这个状态。虽然有点乱，但也能工作。下面给出了一个例子：
var maximum = 0
func MaxGlobalVariable(node *node) {
if node == nil {
return
}
if node.value > maximum {
maximum = node.value
}
MaxGlobalVariable(node.left)
MaxGlobalVariable(node.right)
}
func main() {
maximum = int(math.MinInt)
MaxGlobalVariable(ExampleTree)
fmt.Println(maximum)
}
前面的代码肯定谈不上理想。首先我们不鼓励使用全局变量来跟踪任何状态。多线程并发的时候会引出很多麻烦，尤其是忘了在递归调用之前重置变量的情况下。即便是在单线程情况下产出也是不可靠的。
另一种更好的方法是跟踪当前的最大值，作为递归调用的一部分。我们要扩展函数签名，使之包含我们要跟踪的整数值：
func.maxInline(node *node, maxValue int) int {
if node == nil {
return maxValue
}
if node.value > maxValue {
maxValue = node.value
}
maxLeft := maxInline(node.left, maxValue)
maxRight := maxInline(node.right, maxValue)
if maxLeft > maxRight {
return maxLeft
}
return maxRight
}这里我们通过每次递归调用中传递的maxValue变量来跟踪最大值。每次调用的时候，我们先比较maxValue和当前节点值的大小，然后再比较左右两个子节点的值大小，返回其中较大的值。
如果不看调用时的样子，这可能是最清楚的递归写法了。如果我们调用maxInline函数，看起来就像下面这样：
func main() {
fmt.Println(maxInline(ExampleTree, 0))
}
在对maxInline的调用中，实现的细节泄露给了调用者，调用者需要给递归函数传递一个初始值。这样就增加了复杂度。而对于更加复杂的情况，我们还没法指望调用者知道什么才是合适的初始值。理想情况下，我们不应该将这种状态细节泄露给调用者。传统的面向对象语言解决这个问题靠的是，暴露一个公开的非递归函数，在其中调用私有的递归函数并带上状态。如果在Go中模拟，那就是下面这样：
func main() {
fmt.Println(MaxInline(ExampleTree))
}
func MaxInline(root *node) int {
return maxInline(root, 0)
}
func maxInline(node *node, maxValue int) int {
if node == nil {
return maxValue
}
if node.value > maxValue {
maxValue = node.value
}
maxLeft := maxInline(node.left, maxValue)
maxRight := maxInline(node.right, maxValue)
if maxLeft > maxRight {
return maxLeft
}
return maxRight
}
这里我们创建了一个公开的MaxInline函数，没有暴露maxInline的内部机制。调用者只需要提供根节点就可以了。这个函数会带着正确的初始值调用maxInline函数。这个模式在面向对象语言中是很常见的，如果那些语言不支持头等函数，那这便是正确的做法。
然而在Go中，我们可以做的更好。前面这个方法的问题在于包的私有空间中还是多出来了一个大家都能用的函数。有时可能会故意设计成这样，但并不总是如此。解决办法也不是没有，可以将递归函数包裹在非递归函数内部。这样我们可以在非递归函数内部跟踪状态，而其又能被内层的递归函数访问到。
下面的实现便是这么做的：
func Max(root *node) int {
currentMax := math.MinInt
var inner func(node *node)
inner = func(node *node) {
if node == nil {
return
}
if node.value > currentMax {
currentMax = node.value
}
inner(node.left)
inner(node.right)
}
inner(root)
return currentMax
}
让我们看下这里发生了什么。首先Max函数本身不是递归的，我们如果需要执行别的什么操作，在这里就行，比如记日志、添加性能指标、状态等等。在我们的场景中，我们创建了一个变量叫做currentMax，用来跟踪当前我们所遇到的最大值。
接下来创建的变量inner，类型是func(node *Node)。这是一个很重要的步骤。我们并不是直接内联创建这个函数，而是先创建了一个变量，不着急附着函数。之所以这样做，是为了后续在匿名函数中可以引用inner变量。
接下来便是实例化这个inner函数，结合起来便是下面这样：
var inner func(node *node)
inner = func(node *node) {
if node == nil {
return
}
if node.value > currentMax {
currentMax = node.value
}
inner(node.left)
inner(node.right)
}
这展示了在inner内部调用inner(node.left) 和inner(node.right)。如果我们没有提前定义变量，像下面这样的代码就执行不了：
inner := func(node *node) {
if node == nil {
return
}
if node.value > currentMax {
currentMax = node.value
}
inner(node.left)
inner(node.right)
}
这看起来只是个小改动，但却会破坏我们的函数。毕竟，如果编译器还没有编译这个函数，它该如何引用inner呢？
代码的最后一步便是调用内部的递归函数：
inner(root)在这个例子中，我们看到了如何使用头等函数来帮我们编写递归函数。但这样还是会有性能影响，我们会在下面的章节中探索。
递归函数的限制
递归函数是有性能损失的。当创建递归函数的时候，我们需要将函数状态复制到栈帧中。这涉及到数据向工作内存的复制，而且还需要额外的开销来让函数调用生效。递归方案的主要限制，至少在Go中，是递归调用会耗尽内存空间。别的限制还有递归的方案比迭代的慢。
衡量递归式与迭代式方案的性能
在我们查看递归函数调用的空间影响之前，先来比较一下，内存允许的情况下递归和循环的性能差异。为了展示这一点，我们会使用本篇开头的阶乘函数解决同样的问题：
package pkg
func IterativeFact(n int) int {
result := 1
for i := 2; i <= n; i++ {
result *= i
}
return result
}
func RecursiveFact(n int) int {
if n == 0 {
return 1
}
return n * RecursiveFact(n-1)
}
为了测试这两个函数，我们可以使用Go的性能测试工具，前面的篇章中也有提及。工具的设置是比较直白的：
package pkg
import "testing"
func BenchmarkIterative100(b *testing.B) {
for n := 0; n < b.N; n++ {
IterativeFact(10)
}
}
func BenchmarkRecursive100(b *testing.B) {
for n := 0; n < b.N; n++ {
RecursiveFact(10)
}
}
我们计算10的阶乘来测试两者的性能。这个问题只需要10步就能解决，开销不大，但是足以展示性能的影响了。多次运行后的平均结果如下：
图中展示了递归函数不仅整体比循环函数更慢，而且随着计算量增加，慢的更多。所以写递归函数的时候务必要考虑这一点。
性能测试注意点
这些结果是在亚马逊AWS的EC2实例上跑出来的。实际的值取决于电脑的情况。在不同的电脑上可能会得到不同的数值，但是整体的趋势应该是一样的。即便是同一台机器多次运行，结果也可能有波动。
递归函数的空间限制
除了一般场景中跑的更慢，递归函数还有另一个缺点：每次函数调用都会增加栈帧到栈空间中。回顾图7.1，这些栈帧是以LIFO的模式叠加起来的。一旦栈空间到头了，程序就停了。好消息是，在Go中，这个限制放的较宽，可能不会有太多的影响。在现代的64位机器上，栈可以容纳1GB的数据，而32位的机器只有250MB。
实践中这个限制也不是没可能触及，我们看下面的例子：
func main() {
infiniteCount(0)
}
func infiniteCount(i int) {
if i%1000 == 0 {
fmt.Println(i)
}
infiniteCount(i + 1)
}
如果我们在32位的机器上运行这个函数，输出的尾部就会如下面这样：
1861000
1862000
1863000
1864000
runtime: goroutine stack exceeds 262144000-byte limit
runtime: sp=0xc008080380 stack=[0xc008080000, 0xc010080000]
fatal error: stack overflow
runtime stack:
runtime.throw({0x496535?, 0x50e900?}) /usr/lib/golang/src/runtime/panic.go:992 +0x71
runtime.newstack() /usr/lib/golang/src/runtime/stack.go:1101 +0x5cc
runtime.morestack() /usr/lib/golang/src/runtime/asm_amd64.s:547 +0x8b经过了180万次迭代，程序终于挂了。实际的限制取决于每个栈帧有多大。对于更加复杂、管理状态更多的递归函数，这个天花板就更低了。那我们如何才能避免这个限制呢？在Go中，没有办法能完全避免递归函数的这个限制。不过我们还是可以调整这个限制，使用debug.SetMaxStack(bytes)函数。作为展示，我们将32位机器上的空间设置为默认的两倍。
func main() {
debug.SetMaxStack(262144000 * 2)
infiniteCount(0)
}
func infiniteCount(i int) {
if i%1000 == 0 {
fmt.Println(i)
}
infiniteCount(i + 1)
}
现在程序在内存耗尽之前可以坚持得更久了。
3724000
3725000
3726000
3727000
3728000
runtime: goroutine stack exceeds 524288000-byte limit
runtime: sp=0xc010080388 stack=[0xc010080000, 0xc020080000]
fatal error: stack overflow
runtime stack:
runtime.throw({0x496535?, 0x50e900?}) /usr/lib/golang/src/runtime/panic.go:992 +0x71
runtime.newstack() /usr/lib/golang/src/runtime/stack.go:1101 +0x5cc
runtime.morestack() /usr/lib/golang/src/runtime/asm_amd64.s:547 +0x8b程序在触及500MB的限制之前，完成了370万次迭代。尽管32位上的250MB不够用，但是64位上的1GB一般是够用了。
使用尾递归来解具栈的限制
考虑到递归有如此多的限制，函数式语言还倾向于递归而非循环就很奇怪了。通常在这种语言，比如Haskell中，只有递归函数，而且还用它来模拟循环。这里我们要看看Haskell这样的语言是如何让递归工作的。
注意：写作之时，Go还不支持这一点。
有些函数式语言用到的技术叫做尾递归优化。即便不是函数式语言也有可能提供这个，最知名的是Javascript。这是一种编译器（解释器）优化手段，不需要分配新的栈帧就能调用递归函数。还记得递归函数的主要缺陷是耗尽栈空间吗？如果我们能解决这个问题，就能无限递归了。
编译器也需要程序员的一些配合来让其生效。我们虽然会用Go来展示，但要记住，目前Go的编译器还不支持这个优化，最终仍然会耗尽栈空间。
将函数重写为尾递归调用
尾递归调用函数和普通递归函数的主要区别在于尾调用变量，每个栈帧和其它无关。为了展示这一点，再看一次下面的阶乘函数：
func Fact(input int) int {
if input == 0 {
return 1
}
return input * Fact(input-1)
}
函数的最后一行，我们返回input * Fact(input – 1)，这将每次调用的结果与后续调用的结果关联了起来。为了对这个乘法求值，我们需要先执行下一层的Fact函数。我们可以重写这个函数，使得每个栈帧独立于其它的栈帧。
为此，我们需要再次用到头等函数。我们会创建一个外层函数，tailCallFactorial，非递归的，由其调用内层的递归函数factorial。
为了将递归函数的每个栈帧独立开来，我们做出两个改动。第一，添加一个计数器，从input倒数至0，这等价于for i := n; i > 0; i --的循环；第二，持续聚合每次乘法的结果。我们通过
func tailCallFactorial(n int) int {
var factorial func(counter, result int) int
factorial = func(counter, result int) int {
if counter == 0 {
return result
}
return factorial(counter-1, result*counter)
}
return factorial(n, 1)
}
其中让这个函数称为尾递归函数的关键一句是：
return factorial(counter-1, result*counter)
通过这个简单的变化，每个栈帧都可以独立求值。有的编译器还能检测到这一点，在调用下一个栈帧的时候回收当前的栈帧。这是对尾递归优化的概要介绍，不过要记住目前Go还不支持这种编译器优化。
总结
本片中我们看到了递归为什么会成为函数式编程语言的核心部分。我们看到递归函数如何强化函数的纯粹性和不可变性的。接下来我们看到了头等函数让递归调用的状态管理更加简单。我们创建了一个外层的非递归函数，由其调用内层的递归函数来执行计算。
后面我们探讨了递归和迭代方案的性能考虑。我们看到了递归方案常常要比循环的方案更慢。而且递归函数还有可能耗尽内存，让程序挂掉。
最后我们了解了尾递归优化和尾递归函数。尾递归优化是一种特殊的编译器优化，许多语言，比如Haskell和Javascript都支持，来解决递归函数的限制。而关键的是，Go目前并不支持这一点，即便我们写了尾递归函数也没有用。
下一篇中，我们会一起来看声明式编程。我们会利用递归来写一种持续传递型的程序。