描述

当一个函数调用发生时，电脑必须 “记住” 调用函数的位置 — 返回位置，才可以在调用结束时带着返回值回到该位置，返回位置一般存在调用栈上。在尾调用的情况中，电脑不需要记住尾调用的位置而可以从被调用的函数直接带着返回值返回调用函数的返回位置（相当于直接连续返回两次），尾调用消除即是在不改变当前调用栈（也不添加新的返回位置）的情况下跳到新函数的一种优化（完全不改变调用栈是不可能的，还是需要校正调用栈上形参与局部变量的信息。）

对函数调用在尾位置的递归或互相递归的函数，由于函数自身调用次数很多，递归层级很深，尾递归优化则使原本 O(n) 的调用栈空间只需要 O(1)。因此一些编程语言的标准要求语言实现进行尾调用消除，例如Scheme与ML家族的语言。在Scheme中，语言标准还将尾位置形式化，指定了各种语法中允许尾调用的地方。

以Python为例，主要区分普通递归和尾递归对栈空间的使用：

defrecsum(x):ifx==1:returnxelse:returnx+recsum(x-1)

调用recsum(5)为例，SICP中描述了相应的栈空间变化：

recsum(5)5+recsum(4)5+(4+recsum(3))5+(4+(3+recsum(2)))5+(4+(3+(2+recsum(1))))5+(4+(3+(2+1)))5+(4+(3+3))5+(4+6)5+1015

可观察，堆栈从左到右，增加到一个峰值后再计算从右到左缩小，这往往是我们不希望的，所以在C语言等语言中设计for, while, goto等特殊结构语句，使用迭代、尾递归，对普通递归进行优化，减少可能对内存的极端消耗。修改以上代码，可以成为尾递归：

deftailrecsum(x,running_total=0):ifx==0:returnrunning_totalelse:returntailrecsum(x-1,running_total+x)

或者使用迭代：

foriinrange(6):sum+=i

对比后者尾递归对内存的消耗：

tailrecsum(5,0)tailrecsum(4,5)tailrecsum(3,9)tailrecsum(2,12)tailrecsum(1,14)tailrecsum(0,15)15

则是线性的。

语法上的表现

尾调用可能位于一个函数语法上最后的位置：

functionfoo(data){a(data);returnb(data);}

在这里，a(data)、b(data) 都是函数调用，但是 b(data) 是函数返回前的最后运行的东西，所以也是所谓的尾位置。然后，并非所有的尾调用都必须在一个函数语法上最后的位置。考虑：

functionbar(data){if(a(data)){returnb(data);}returnc(data);}

在这里，b、c 的调用都在尾位置。这是因为尽管 b(data) 不在 bar 语法上最后的位置，它是 if 叙述其中一个分支最后的位置。

现在考虑以下代码：

functionfoo1(data){returna(data)+1;}

functionfoo2(data){varret=a(data);returnret;}

functionfoo3(data){varret=a(data);return(ret===0)?1:ret;}

在这里，a(data) 处于 foo2 的尾位置，但不处于 foo1 或 foo3 的尾位置。这是因为程序必须返回这两个 a 函数的调用以检查、更动 a 的返回值。

然而，对于 C++ 等语言来说，在函数最后 return g(x); 并不一定是尾递归——在返回之前很可能涉及到对象的析构函数，使得 g(x) 不是最后执行的那个。这可以通过返回值优化来解决。

实例

通常被用于解释递归的程序是计算阶乘。以下计算阶乘的Scheme程序不是尾部递归，而只是一般递归：

(define (factorialn)(if (= n1)1(* n(factorial(- n1)))))

因此，如果调用 factorial 时的参数 n 足够大，这一程序会出现堆栈溢出。然而，如果将同一程序写作尾部递归，按 Scheme 的标准将不会出现溢出：

(define (factorialn)(define (iterproductcounter)(if (> countern)product(iter(* counterproduct)(+ counter1))))(iter11))

在第二个程序中，注意 iter 函数直接返回其递归调用，而没有对其进行运算。因此，这是一个尾部递归，这让直译器或编译器将本来是

的运行过程组合成在时间、空间上性能都较好的类型：

因为在中间过程中重复使用 iter 的函数帧，这种重组节省了空间。这也代表程序员不需要为了担心栈空间或是堆空间用完。在一般的实现中，尾部递归的型态也比其他型态更快速，不过仅仅是常量倍数的差异（非指数差异）。

很多使用函数语言的程序员会为了使用这个优化将递归的代码写成为尾部递归的形式。这通常需要一个多出来代表 “搜集器” 的形参（上述例子的 product 参数）。在一些语言中的一些函数的实现中（像是过滤一个列的实现等等），如果要使用尾部递归则需要将本来没有副作用的纯函数改写成会更动其他参引的形式。

实现

在Perl里，程序员可以直接用一种带有函数名称的 “goto” 叙述变体：goto &NAME; 直接使用尾调用。

在程序语言实现中，消除尾递归里的尾调用比消除一般的尾调用容易很多。举里来说，Java 虚拟机（JVM）的实现会消除尾递归里的尾调用（因为重新使用了原来的调用栈），但是不会消除一般的尾调用（因为改变了的调用栈）。因此，Scala等等使用 JVM 平台的函数语言可以有效的实现一个函数的尾递归，但是两个函数以上的尾递归就不行。

尾递归的实现方法有几个：

汇编重组

对于直接生成汇编的编译器，尾部调用消除很简单：只要校正栈上的形参之后把 “call” 的机器码换成一个 “jump” 的就行了。从编译器的观点，以下代码

先会被翻译成（这是合法的 x86 汇编）：

然后，尾部调用消除指的是将最后两个指令以一个 “jump” 指令替换掉：

在 a 函数完成的时候，它会直接返回到 foo 的返回地址，省去了不必要的 ret 指令。

函数调用可能带有参数，因此生成的汇编必须确保被调用函数的函数帧在跳过去之前已设置好。举例来说，若是平台的调用栈除了返回位置以外还有函数参数，编译器需要输出调整调用栈的指令。在这类平台上，考虑代码：

其中 data1、data2 是参数。编译器会把这个代码翻译成以下汇编：

尾部调用优化会将代码变成：

更改后的代码不管在执行速度或是栈空间的使用上的性能都比较好。

透过弹跳床

然而，由于很多Scheme的编译器使用C作为中间目标语言，问题变成如何在 C 里在不让栈向上长的前提下实现尾部递归（假设 C 的编译器不优化尾部调用）。很多实现透过一种叫做弹跳床的装置，也就是一块不断进行函数调用的代码。所有进入函数的过程都透过这个弹跳床。当一个个函数需要尾部调用另一个函数时，它不是直接调用该函数，而是将该函数的位置、该调用使用的参数等等返回给弹跳床。这样就可以确保 C 的栈不会不会向上长而可以让循环继续运行。

用Groovy、Visual Basic .NET、C#等等支持高阶函数的语言实现弹跳床是可能的。

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。