正确的尾递归
 |
||
|
正确的尾递归 |
|
function f(args)
...
return g(args2)
end
有时递归函数可以改写成尾递归版本。例如，阶乘函数的通常定义会得到：
function fact(n) if (n==0) then return 1 else return n*fact(n-1) end end
这不是尾递归，因为最后要进行的计算是 n 和 fact(n-1) 的乘积。但下面这个是：
function factt(n) return fact_(n, 1) end function fact_(n, ans) if (n==0) then return ans else return fact_(n-1, n*ans) end end
这两个定义在给定相同参数的情况下，结果完全相同。
> = fact(5) 120 > = factt(5) 120但幕后情况有所不同。如果我们以非预期的方式使用这些函数，就会发现这种差异。上面的朴素实现只适用于正整数。如果给定负数或分数结果，它们可能会陷入无限递归。
如果我们执行 fact(-1)，最终会得到一个栈溢出消息。
> = fact(-1)
stdin:1: stack overflow
stack traceback:
stdin:1: in function `fact'
stdin:1: in function `fact'
...
stdin:1: in function `fact'
(tail call): ?
[C]: ?
另一方面，如果我们调用 factt(-1)，它永远不会返回（这更类似于对函数体的数学分析）。
正确的尾递归是关于经济性，这对 Lua 所针对的应用类型非常重要。作为一种优化，调试变得更加困难，因为无法重建调用跟踪。
每当语言规范说实现了正确的尾递归时，就意味着承诺在尾函数调用的特殊情况下不会浪费栈。这是语言设计者为用户提供的质量契约。这在计算机科学界很常见：Scheme、Perl、Forth 等语言也这样做。如果你的最喜欢的编程语言没有这样做，请投诉。
这是一篇入门文本。它旨在说明该特性作为 Lua 的特性，并可能在函数调用教程中提到。