Go语言没有优化递归操作的原因是什么呢？

有些人不太明白什么是递归操作。 其实可以用简单的方式来解释，那就是函数调用自身。 那么为什么我们需要编写一个函数来调用自己呢？ 例如，递归算法在使用堆栈（先进后出）进行数据操作时非常方便。 它比循环操作更快，并且具有良好的代码简洁性。

在进行数学运算时，典型的递归场景是：当前计算结果是下一次计算的输入。 与所有递归操作一样，您必须设置一个() 来触发递归函数的结束并返回结果。 如果不这样做，递归函数就会进入死循环，最终导致内存溢出。

为什么你的程序会导致内存溢出？ 在传统的C语言程序中，堆栈内存是处理所有函数调用的地方，因为堆栈是一种预先分配的内存，并且速度非常快。 例如如下所示：

上图描绘了堆栈内存的典型示例，它可能与我们编写的所有程序类似。 从图中可以看出，堆栈内存会随着函数调用而增加。 每次我们从函数中调用另一个函数、变量、寄存器和数据时，这些参数地址或变量名总是会被压入堆栈，从而增加其内存。

在C程序中，每个线程本身都有一定的堆栈内存空间。 根据结构的不同，栈内存的大小当然也不同，从1M到8M不等。 当然，你也可以调整默认值。 如果您编写一个产生大量线程的程序，您将很快耗尽您不太可能使用的内存。

在 Go 程序中，每个堆栈内存都是分配的，但 Go 更聪明：最初分配 4K，并根据需要增长。 Go语言能够动态增加堆栈内存的概念来自于split（堆栈分割）。 更多拆分内容请前往：

/维基/

还可以参考Go语言包中的如下堆栈实现代码：

当你想使用递归时，你需要意识到堆栈内存不断增加，直到达到你设置的点，并且它的内存开始减少。 当我们说Go不优化递归操作时，我们需要承认一个事实：Go并没有尝试优化无限增加堆栈内存的操作。 这就是尾部调用登场的时候。

在介绍尾调用如何优化递归函数之前，我们先看一个简单的递归函数：

func Recursive(number int) int {
    if number == 1 {
        return number
    }
    return number + Recursive(number-1)
}
func main() {
    answer := Recursive(4)
    fmt.Printf("Recursive: %d\n", answer)
}

上面的递归函数需要传入一个整数作为参数并返回一个整数。 如果传入函数的值为1，函数将立即返回。 这个if函数包含了锚点，并使用堆栈来完成执行任务。

如果传入的变量不为1，则递归函数将开始工作。 递归函数将参数值减1，然后将减后的参数作为下一次递归调用的参数。 堆栈内存随着每次函数调用而增加，直到到达锚点并且所有递归调用开始返回到主函数。

我们来看看上图中所有的函数调用和返回值是如何工作的：

该流程图展示了从左下角开始，从下到上递归操作的详细调用链。 主函数调用递归函数并传入参数4，然后递归函数调用自身并传入参数3。如此反复调用，直到将参数值1传入递归函数。 递归函数之前调用自身3次，当到达锚点时，每次调用操作对应有3个扩展栈帧。 然后递归开始，真正的工作开始。 从图中可以看出，扩展操作是在右侧从上到下进行的。 每个操作通过获取参数并将它们添加到函数调用的返回值来执行每个返回操作。 执行最后一次操作后，我们得到最终答案 10。

递归函数非常快地执行这些步骤，所以这就是递归的好处，我们不需要任何迭代或循环计数。 堆栈存储当前结果并将其返回给前一个函数。 当然，我们唯一需要担心的是我们需要消耗多少内存。

什么是尾调用？ 它如何优化递归函数？ 接下来，我们将创建一个带有尾调用的递归函数，看看它是如何解决递归函数消耗大量堆栈内存的问题的。

这是相同的递归函数，但通过尾调用实现：

func TailRecursive(number int, product int) int {
    product = product + number
    if number == 1 {
        return product
    }
    return TailRecursive(number-1, product)
}
func main() {
    answer := TailRecursive(4, 0)
    fmt.Printf("Recursive: %d\n", answer)
}

你能看出它们之间的区别吗？ 这与我们如何使用堆栈和计算结果有关。 在这个实现中，锚实际上返回的是最终结果！ 除了最终值之外，我们不再需要堆栈中的任何返回值。

一些编译器能够看到这种微妙的差异，并更改生成的底层程序集，以对所有递归调用使用一个堆栈帧。 Go 编译器还无法检测到这种细微的差异。 为了证明这一点，让我们看一下 Go 编译器为这两个函数生成的汇编代码。

为了生成汇编代码，您可以在终端中执行以下命令：

go tool 6g -S ./main.go > assembly.asm

根据您的机器架构，通常有三个编译器。

如果需要了解更多架构或者其他Go工具命令，可以移步到：/cmd/gc/

我在下面列出了 Go 代码和汇编代码。 希望其中之一能帮助您理解。

为了使处理器能够对数据进行操作，例如加法或数值比较，数据必须存储在寄存器中。 你可以想一下寄存器是如何处理变量的。 当你看下面的汇编代码时，你就会明白AX和BX是主要的寄存器，而且它们的使用频率很高。 SP寄存器是堆栈指针，FP寄存器是帧指针，也与堆栈有关。

那么，让我看一下下面的代码：

07 func Recursive(number int) int {
08
09     if number == 1 {
10
11         return number
12     }
13
14     return number + Recursive(number-1)
15 }
— prog list "Recursive" —
0000 (./main.go:7) TEXT Recursive+0(SB),$16-16
0001 (./main.go:7) MOVQ number+0(FP),AX
0002 (./main.go:7) LOCALS ,$0
0003 (./main.go:7) TYPE number+0(FP){int},$8
0004 (./main.go:7) TYPE ~anon1+8(FP){int},$8
0005 (./main.go:9) CMPQ AX,$1
0006 (./main.go:9) JNE ,9
0007 (./main.go:11) MOVQ AX,~anon1+8(FP)
0008 (./main.go:11) RET ,
0009 (./main.go:14) MOVQ AX,BX
0010 (./main.go:14) DECQ ,BX
0011 (./main.go:14) MOVQ BX,(SP)
0012 (./main.go:14) CALL ,Recursive+0(SB)
0013 (./main.go:14) MOVQ 8(SP),AX
0014 (./main.go:14) MOVQ number+0(FP),BX
0015 (./main.go:14) ADDQ AX,BX
0016 (./main.go:14) MOVQ BX,~anon1+8(FP)
0017 (./main.go:14) RET ,

如果我们顺着汇编代码看，你会发现栈无处不在：

汇编代码显示我们正在进行递归调用，并且值正在按预期从堆栈中压入和弹出。 堆栈内存在增加的同时被释放。

现在，让我们为包含尾调用的递归函数生成汇编代码，看看 Go 编译器是否优化了任何内容。

17 func TailRecursive(number int, product int) int {
18
19     product = product + number
20
21     if number == 1 {
22
23         return product
24     }
25
26     return TailRecursive(number-1, product)
27 }
— prog list "TailRecursive" —
0018 (./main.go:17) TEXT TailRecursive+0(SB),$24-24
0019 (./main.go:17) MOVQ number+0(FP),CX
0020 (./main.go:17) LOCALS ,$0
0021 (./main.go:17) TYPE number+0(FP){int},$8
0022 (./main.go:17) TYPE product+8(FP){int},$8
0023 (./main.go:17) TYPE ~anon2+16(FP){int},$8
0024 (./main.go:19) MOVQ product+8(FP),AX
0025 (./main.go:19) ADDQ CX,AX
0026 (./main.go:21) CMPQ CX,$1
0027 (./main.go:21) JNE ,30
0028 (./main.go:23) MOVQ AX,~anon2+16(FP)
0029 (./main.go:23) RET ,
0030 (./main.go:26) MOVQ CX,BX
0031 (./main.go:26) DECQ ,BX
0032 (./main.go:26) MOVQ BX,(SP)
0033 (./main.go:26) MOVQ AX,8(SP)
0034 (./main.go:26) CALL ,TailRecursive+0(SB)
0035 (./main.go:26) MOVQ 16(SP),BX
0036 (./main.go:26) MOVQ BX,~anon2+16(FP)
0037 (./main.go:26) RET ,

包含尾部调用的函数会生成更多汇编代码。 然而，结果非常相似。 事实上，从性能的角度来看，我们让事情变得更糟。

Go 没有对我们实现的尾部调用进行任何优化。 我们仍然执行与前面的示例相同的堆栈操作和递归调用。 所以我猜 Go 目前还没有针对递归进行优化。 这并不意味着我们不应该使用递归，我们只需要知道Go语言中提供了这个功能即可。

如果你有一个问题可以通过递归算法完美解决，但又害怕浪费内存，那么你可以考虑使用操作。 不过，这个操作从某种意义上来说会慢很多，但确实解决了你的顾虑。 以下是如何使用通道实现递归函数：

func RecursiveChannel(number int, product int, result chan int) {
    product = product + number
    if number == 1 {
        result <- product
        return
    }
    Go RecursiveChannel(number-1, product, result)
}
func main() {
    result := make(chan int)
    RecursiveChannel(4, 0, result)
    answer := <-result
    fmt.Printf("Recursive: %d\n", answer)
}

它也是使用尾调用来实现的。 一旦命中，就会生成最终答案并将答案放入通道中。 它不是进行递归调用，而是生成一个提供与我们在尾部调用示例中推入堆栈的相同状态的递归调用。

唯一的区别是我们将一个无缓冲的传递给 . 只有锚点可以将数据写入通道，它不执行任何其他操作。

在主函数中，创建一个无缓冲通道，并使用初始参数和通道调用该函数。 该函数立即返回，但 main 不会终止，因为它等待数据写入通道。 一旦锚点被命中并且答案被写入通道，主函数就会被唤醒并将结果打印到屏幕上。 在大多数情况下，main 会在终止之前唤醒。

递归是编写 Go 程序时可以使用的另一个工具。 目前，Go 编译器没有优化尾部调用代码，但是 Go 的未来版本没有理由不优化这个问题。 如果内存大小是你程序运行时考虑的因素，那么你不妨模拟一下递归操作。

via：Go语言中的递归和尾调用操作 - Go语言中文网 - 中文社区

作者： 译者： 校对者：

本文由 GCTT 原创编译，Go 语言中文网自豪推出