简介

一般来说，一个函数 (caller) 在调用另外一个函数 (callee) 之前，需要把一些寄存器保存到栈上，因为被调用的那个函数 (callee) 有可能会修改寄存器，而把这些寄存器提前保存可以使得在对 callee 的调用返回之后 caller 仍然能够恢复这些寄存器。

当一个函数调用另外一个函数时它需要一些栈上的空间保存寄存器的值，而如果被调用的那个函数自身也要调用函数，它也需要一些栈空间来保存寄存器，像这样推广下去，当调用链足够长的时候，因为内存是有限的，所以最终会发生栈溢出 (stack-overflow) 问题，即：栈空间和其他内存区域重合（一次 push 操作需要减小 esp 栈指针寄存器内保存的值），或者说栈空间超过 ulimit 命令行设定的限制。

然而，聪明的编译器开发人员注意到：在某种情况下能够不需要为嵌套的函数调用分配栈空间，换言之，可以将一类特殊的递归函数转换成迭代式的（并且在不影响程序行为的前提下）。

尾调用和尾递归

如果一个函数体返回语句之前的最后一条语句执行的是一个函数调用，我们说这个函数是尾调用 (tail-call) 的。

如果一个函数是尾调用的，并且那个函数调用调用的是它自己，则我们说这个函数是尾递归的 (tail-recursion).

显然，若一个函数是尾递归的，那么它一定是尾调用的，反之则未必成立。

我们用递归实现的阶乘函数 fact 举例：

以下这个阶层函数实现不是尾递归的（它甚至都不是尾调用的）：

long fact(long n) {
  if (n == 0)
    return 1;
 
  return n * fact(n-1);
}

因为它返回之前，最后一条语句应该是乘法：把 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 实现：

long fact(long n, long prod) {
  if (n == 0)
    return prod;
  return fact(n-1, n * prod);
}

在 C/C++ 中，编译器在翻译函数调用语句时，会先翻译函数实参的求值语句，因此，对 fact 函数的调用（或跳转）一定是在参数求值完毕后执行的，因此，我们能够有把握地说：这样的 fact 函数实现是尾调用，并且是尾递归的。

尾调用（尾递归）对代码生成的影响

有意思的是，在 x86-64 clang 15.0.0 编译器下，以 std=c++17 -O1 作为编译器参数，第一份 fact 实现翻译得到的汇编是：

fact(long):                               
        mov     eax, 1
        mov     rcx, rdi
        sub     rcx, 1
        jb      .LBB0_3
.LBB0_2:                                
        imul    rax, rdi
        mov     rdi, rcx
        sub     rcx, 1
        jae     .LBB0_2
.LBB0_3:
        ret