尾调用

在计算机学，尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接作為当前函数的返回结果。

特征与简单示例
尾调用可能位于一个函数语法上最后的位置：

function foo(data) {
a(data);
return b(data);
}

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

function bar(data) {
if ( a(data) ) {
return b(data);
}
return c(data);
}

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

现在考虑以下代码：

function foo1(data) {
return a(data) + 1;
}

function foo2(data) {
var ret = a(data);
return ret;
}

function foo3(data) {
var ret = a(data);
return (ret === 0) ? 1 : ret;
}

在这里，a(data) 处于 foo2 的尾位置，但不处于 foo1 或 foo3 的尾位置。这是因為程序必須返回這2個 a 函數的调用以檢查、更動 a 的返回值。

说明
传统模式的编译器对于尾调用的处理方式就像处理其他普通函数调用一样，总会在调用时创建一个新的栈帧（stack frame）并将其推入调用栈顶部，用于表示该次函数调用。）

由于当前函数帧上包含局部变量等等大部分的东西都不需要了，当前的函数帧经过适当的更动以后可以直接当作被尾调用的函数的帧使用，然后程序即可以跳到被尾调用的函数。产生这种函数帧更动代码与 “jump”（而不是一般常规函数调用的代码）的过程称作尾调用消除（Tail Call Elimination）或尾调用优化（Tail Call Optimization，TCO）。尾调用优化让位于尾位置的函数调用跟 goto 语句性能一样高，也因此使得高效的结构编程成为现实。

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

尾递归
若函数在尾位置调用自身（或是一个尾调用本身的其他函数等等），则称这种情况为尾递归。尾递归也是递归的一种特殊情形。尾递归是一种特殊的尾调用，即在尾部直接调用自身的递归函数。对尾递归的优化也是关注尾调用的主要原因。尾调用不一定是递归调用，但是尾递归特别有用，也比较容易实现。

特点
尾递归在普通尾调用的基础上，多出了2个特征：

• 在尾部调用的是函数自身 （Self-called）；
• 可通过优化，使得计算仅占用常量栈空间 (Stack Space)。

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

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

def recsum(x):
if x == 1:
return x
else:
return x + 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 + 10
15

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

def tailrecsum(x, running_total=0):
if x == 0:
return running_total
else:
return tailrecsum(x - 1, running_total + x)

或者使用迭代：

for i in range(6):
sum += i

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

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

则是线性的。

优化尾调用的不同方式
要方便地实现尾调用优化，一般需借助编译器或运行环境提供的现成的尾递归优化特性，或是依赖所用程序语言能直接支持更底层的指令跳转。

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

在程序语言实现中，消除尾递归里的尾调用比消除一般的尾调用容易很多。举例来说，Java 虚拟机（JVM）的实现会消除尾递归里的尾调用（因为重新使用了原来的调用栈），但是不会消除一般的尾调用（因为改变了的调用栈）。Scala 等同样基于 JVM 平台的语言可以有效地实现单个函数的尾递归优化，但是对于多个函数的相互尾递归就无法优化了。

JavaScript则原本不支持尾调用优化，到其第6代语言核心标准“ECMAScript 6”开始规定程序引擎应在严格模式下使用尾调用优化。而且ECMAScript 6限定了尾位置不含闭包的尾调用才能进行优化。。

对所有函数调用使用弹跳床，相比常规的C调用有着高昂的开销，所以至少有一个Scheme编译器即Chicken，使用了首先由听从未发表建议而描述的一种技术。在其中使用常规的C调用，但是在每次调用前检查栈的大小。当栈达到它的最大允许大小的时候，在栈上的对象经由Cheney算法而被垃圾回收，所有存活数据都将移动到分立的堆之内。随后栈被回缩（弹出），而程序恢复到紧邻垃圾回收之前保存的状态。Baker声称：“Appel的方法通过偶尔的跳下帝国大厦而避免了大量的小型蹦床弹跳”：

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

因此，如果呼叫 factorial 時的參數 n 足夠大，這一程式會出現堆疊溢位。然而，如果將同一程式寫作尾端遞迴，按 Scheme 的標準將不會出現溢位：

(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))

在第2個程式中，注意 iter 函數直接返回其遞迴呼叫，而沒有對其進行運算。因此，這是一個尾端遞迴，这让直译器或编译器将本来是

call factorial (3)
call iter (3 1)
call iter (2 3)
call iter (1 6)
call iter (0 6)
return 6
return 6
return 6
return 6
return 6

的執行過程組合成在時間、空間上性能都較好的型態：

call factorial (3)
call iter (3 1)
将参数变为 (2 3)，跳至 "iter"
将参数变为 (1 6)，跳至 "iter"
将参数变为 (0 6)，跳至 "iter"
return 6
return 6

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

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

注释与资料
註釋
引用
*