作者：ms2008

整理编辑：糖果

在聊今天这个话题之前，我们需要知道什么叫 tail call。先来看下，lua 程序设计是怎么定义的：

尾调用是一种类似在函数结尾的 goto 调用，当函数最后一个动作是调用另外一个函数时，我们称这种调用尾调用。例如：

function f(x)
return g(x)
end

g 的调用是尾调用。

例子中 f 调用 g 后不会再做任何事情，这种情况下当被调用函数 g 结束时程序不需要返回到调用者 f；所以尾调用之后程序不需要在栈中保留关于调用者的任何信息。一些编译器比如 Lua 解释器利用这种特性在处理尾调用时不使用额外的栈，我们称这种语言支持正确的尾调用。

由于尾调用不需要使用栈空间，那么尾调用递归的层次可以无限制的。

是不是有些迷糊？那我继续来解释下「详情可以参考廖雪峰的blog」：

我们知道在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。递归函数的优点是定义简单，逻辑清晰。但是使用递归函数有个要命的缺点就是需要注意防止栈溢出！

在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。可以试试这个求阶乘的用例：

图片

解决递归调用栈溢出的方法是通过尾递归优化。尾递归是指，在函数返回的时候，调用自身本身，并且，return 语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

上面的 fact(n) 函数由于 return n * fact(n - 1) 引入了乘法表达式，所以就不是尾递归了。要改成尾递归方式，需要多一点代码，主要是要把每一步的乘积传入到递归函数中：

图片

可以看到，return fact_iter(n-1, nown) 仅返回递归函数本身，n-1 和 nown 在函数调用前就会被计算，不影响函数调用。

任何递归函数都存在栈溢出的问题。尾递归调用时，如果做了优化，栈不会增长，因此，无论多少次调用也不会导致栈溢出。这也正是 tail call 的威力所在。

遗憾的是，大多数编程语言没有针对尾递归做优化，当然 lua 除外 😃