1
尾调用 (tail-call) 和尾递归 (tail-recursion)
source link: https://hsiaofongw.notion.site/tail-call-tail-recursion-55028db0dd3e4f8cbf4bf1a349b26c74
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Drag image to reposition
尾调用 (tail-call) 和尾递归 (tail-recursion)
Created
February 19, 2023 7:28 AM
tail-call
tail-recursion
c/c++
Description
本文介绍了尾调用和尾递归的概念和区别，并探讨了尾递归优化的原理和优势。尾递归优化可以减少栈空间的使用，提高程序的运行速度，同时还可以提高缓存命中率，具有很好的内存局部性。文章还提供了一些参考资料供读者深入学习。
Updated
July 16, 2023 5:58 AM
3 more properties
一般来说，一个函数 (caller) 在调用另外一个函数 (callee) 之前，需要把一些寄存器保存到栈上，因为被调用的那个函数 (callee) 有可能会修改寄存器，而把这些寄存器提前保存可以使得在对 callee 的调用返回之后 caller 仍然能够恢复这些寄存器。
当一个函数调用另外一个函数时它需要一些栈上的空间保存寄存器的值，而如果被调用的那个函数自身也要调用函数，它也需要一些栈空间来保存寄存器，像这样推广下去，当调用链足够长的时候，因为内存是有限的，所以最终会发生栈溢出 (stack-overflow) 问题，即：栈空间和其他内存区域重合（一次 push 操作需要减小 esp 栈指针寄存器内保存的值），或者说栈空间超过 ulimit 命令行设定的限制。
然而，聪明的编译器开发人员注意到：在某种情况下能够不需要为嵌套的函数调用分配栈空间，换言之，可以将一类特殊的递归函数转换成迭代式的（并且在不影响程序行为的前提下）。
尾调用和尾递归
如果一个函数体返回语句之前的最后一条语句执行的是一个函数调用，我们说这个函数是尾调用 (tail-call) 的。
如果一个函数是尾调用的，并且那个函数调用调用的是它自己，则我们说这个函数是尾递归的 (tail-recursion).
显然，若一个函数是尾递归的，那么它一定是尾调用的，反之则未必成立。
我们用递归实现的阶乘函数 fact 举例：
以下这个阶层函数实现不是尾递归的（它甚至都不是尾调用的）：
因为它返回之前，最后一条语句应该是乘法：把 n 和 fact(n-1) 相乘，它调用之前至少需要把寄存器上的 n 保存到栈上的某个位置，某个 fact(n-1) 不会轻易修改的位置。
读者可能会问：那如果 n 本来就是在栈上保存的呢？别忘了对于足够大的 n, fact(n-1) 会调用 fact(n-2), fact(n-2) 又会调用 fact(n-3), 这些 n-1, n-2, n-3, … 都在栈上，因此栈空间的占用量总是正比于 n 的。
读者可能还会问：那编译器不会把 n 保存到堆上吗？答曰堆上构建的那个对象的地址还是需要保存在栈上的。
以下是一个尾递归版本的 fact 实现：
在 C/C++ 中，编译器在翻译函数调用语句时，会先翻译函数实参的求值语句，因此，对 fact 函数的调用（或跳转）一定是在参数求值完毕后执行的，因此，我们能够有把握地说：这样的 fact 函数实现是尾调用，并且是尾递归的。
尾调用（尾递归）对代码生成的影响
有意思的是，在 x86-64 clang 15.0.0 编译器下，以 std=c++17 -O1 作为编译器参数，第一份 fact 实现翻译得到的汇编是：
Assembly
第二份 fact 实现翻译得到的汇编是：
Assembly
可以看出两份代码高度相似。
具体可参考 Compiler Explorer 页面：
fact(n) 实现
fact(n, prod) 实现
我们能够发现，这两份汇编代码都复用了栈空间，编译器确实会尽可能地帮我们做代码优化。
然而，在一些情况下，编译器并不总是能够为代码做尾递归优化，考察下列两种斐波那契数列的计算函数的实现方式，分别是 fib1 和 fib2:
我们知道，fib1 不是尾递归的，因为它返回之前需要对 fib(n-1) 和 fib(n-2) 的返回值求和，因此它最后一条语句不是对它自身的调用，可是我们前面发现了一个特例：那就是即便函数严格来说不是尾递归的，编译器也能做优化，现在 fib1 不是尾递归的，编译器也能对 fib1 做优化吗？
在 Compiler Explorer 页面，我们看到编译器对 fib1 生成的代码如下：
Assembly
注意到 .LBB0_2 这个 label, 里边只有一个 call fib1(long), 可是在 C++ 代码里边我们调用了两次 fib1, 在 call fib1(long) 下边，又有：
Assembly
也就是说，在执行完对 fib1(n-1) 对调用之后，程序会把返回值 (rax) 加到 r14 寄存器中，然后执行 dec rbx 对 rbx 寄存器递减，我们结合上下文发现 rbx 就是 n, 它在调用 fib1 之前被递减了一次，现在再被递减一次，它的值相当于 n-2，接下来程序执行 test rbx, rbx 和 jne .LBB0_2 判断 rbx 是否等于 0, 若 rbx 不等于 0 则跳转到 .LBB0_2 继续执行，这就相当于调用 fib(n-2) 了，而如果 rbx 等于 0（也就是说 n-2 等于 0), 那么根据我们对这个函数的定义 fib1(0) = 0, 编译器利用这一点直接生成跳转到 .LBB0_4 的代码执行 add r14, r15, 而结合上下文我们知道 r15 等于 0, 因此这也相当于直接拿到 fib1(n-2) 的返回值并且直接加到 fib1(n-1) 上。
所以，我们看到 fib1 还是会被先后调用两次，在 C++ 代码中 fib1 是一个递归函数，并且以一种非尾递归的方式实现，并且编译器没有成功地对它开展尾递归优化。
我们再看编译器为 fib2 函数生成的汇编代码：
Assembly
可以看到编译器已经为 fib2 函数开展了尾递归优化，好处就是这个函数执行时它对栈空间的使用量是 O(1) 的，并且我们阅读汇编代码可知即便传入的 n 特别大，栈空间也不会被消耗完，而且还有一个好处就是计算都是在寄存器上进行的，CPU 不需要从内存（或者缓存）取数据，所以说计算速度非常快！
如果有人要求我们写出计算斐波那契数列的迭代式算法，我们甚至可以理直气壮的回应：开了 -O1 优化的 clang C++ 编译器为一个尾递归函数生成的机器码跑起来未必比迭代式的慢！
尾调用优化原理初探
一般来说，函数在汇编语言中只不过是内存中的一段机器码（反汇编之后看起来就是一段汇编代码，代码的开头处有一个 label，代码段落中间或许也有 label），在调用函数时，编译器需要先生成一系列 push 指令，把各个由 caller 负责保存的寄存器的值保存到栈上，编译器还需要生成一系列 pop 指令置于函数返回之后的位置，用于恢复这些之前保存的寄存器到函数调用之前的状态，不仅如此，编译器还要生成一条指令在函数调用之前，保存这条指令保存返回地址，具体也是 push 到栈上，这样被调用函数执行完毕后才能够知道如何返回。
为什么需要保存这些寄存器的值呢？因为在函数调用指令返回之后，这些寄存器可能还需要继续使用，那如果说，假如编译器知道这些寄存器不需要被保存呢？也就是说假如编译器知道这次函数调用实际上就是这个函数中的最后一条语句（指令），编译器这时还需要生成保存寄存器的指令吗？
实际上是不需要的，而且，由于被调函数 foo 刚好就是自己，也不需要做函数调用了，要执行这个函数，只要跳转过去就行了，这样除了省下了保存寄存器的栈空间外，还省下了保存返回值地址的栈空间，因此读者若仔细观摩 -O1 优化下的编译器为尾递归函数生成的汇编代码，会发现有时候在这个函数体中根本没有 call 和 ret 指令的出现。
因此，尾递归要求在函数对自己的递归调用刚好是返回前的最后一条语句（指令）不是一个巧合，这就是把 call 指令转为各种跳转指令（ jmp, jne, je, jb 等）所要求的：要求函数返回后不再需要使用这些 caller saved 寄存器。
一个函数得以尾递归优化，对它的运行时性能来说通常都是利大于弊的，也就是通常只会更快，不会更慢，原因：
保存寄存器、返回地址需要进行入栈操作，也就是说需要写内存，另外函数返回时还要从栈上取出返回地址，需要读内存，而尾递归优化把这两样都优化掉了；
由于不需要通过栈来传递函数参数与返回值，编译器可以尽可能地把更多变量（甚至全部变量）分配在寄存器上，这样有可能这个函数执行的所有计算都只需要读/写寄存器的值，不需要读/写内存，从而让函数跑起来非常的快；
假如这个函数内部出现了很多很多变量，或者说个别变量的尺寸很大一个寄存器放不下，编译器没法把这么多变量完全分配到数量有限的通用寄存器上，编译器可以把一部分变量分配到栈上，这时，尾递归优化和未进行尾递归优化的差异就显现出来了：
若函数经过了尾递归优化，那么不管函数体被重复执行多少次（迭代多少次），这些变量始终是在栈上的同一个临近区域（在同一个 stack-frame 上，读者可以理解为 stack-frame 没有变），那么这块 stack-frame 有可能会被缓存起来，缓存了之后对 stack-frame 中的变量的读取操作会命中缓存，从而速度快；
而如果函数未经过尾递归优化，那么随着函数递归调用自身的次数（也就是迭代次数）的增加，stack-frame 的位置会改变，而 CPU 的缓存大小是有限的，不可能把每个 stack-frame 都缓存起来了，从而缓存友好性差，具体来说就是缓存命中率低！
我们一般会说，经过尾递归优化的函数有更好的 memory locality, 这是因为它的函数体中的语句多次访问一块儿临近区域的内存（因为它经过尾递归优化之后它的 stack-frame 始终是那个 stack-frame），而不是像未经过尾递归优化的函数那样访问位置相差可能很远的内存区域；
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK