什么是尾递归消除？

Question

Steve Yegge在blog post中提到过它，我不知道它是什么意思，有人可以填补我吗？

与tail call optimization是一样的吗？

Answer 1

尾部呼叫淘汰是一种优化，节省堆栈空间。它取代的功能调用与转到。尾递归消除是同样的事情，但该函数调用自身的制约因素。

基本上，如果最后一件事功能A确实是return A(params...)那么你可以消除堆栈帧的分配，而是设置适当的寄存器并直接跳转到函数的主体中。

考虑一个（虚构）调用约定，该约定传递堆栈上的所有参数并返回某个寄存器中的值。

一些功能可以编译下至（一个虚的汇编语言）：

function: 
//Reading params B, C, & D off the stack 
pop B 
pop C 
pop D 
//Do something meaningful, including a base case return 
... 
//Pass new values for B, C, & D to a new invocation of function on the stack 
push D* 
push C* 
push B* 
call function 
ret 

无论上述实际上并，它占用了每个呼叫起作用的整个新的堆栈帧。然而，由于除了返回之外，在尾部调用之后没有任何操作发生，所以我们可以安全地优化该情况。

在所得：

function: 
//Reading params B, C, & D off the stack (but only on the first call) 
pop B 
pop C 
pop D 
function_tail_optimized: 
//Do something meaningful, including a base case return 
... 
//Instead of a new stack frame, load the new values directly into the registers 
load B, B* 
load C, C* 
load D, D* 
//Don't call, instead jump directly back into the function 
jump function_tail_optimized 

最终的结果是等同功能，节省了大量的堆栈空间，尤其是对于导致大量递归调用的输入。

我的答案中有很多想象力，但我认为你可以明白。

Answer 2

从here：

” ...尾递归消除是尾调用消除 的 特殊情况，其中尾调用是 函数本身在这种情况下， 呼叫的呼叫。可以通过跳转到 启动功能的移动 新的论据，以适当的 寄存器或堆栈位置后更换......”

从Wikipedia：

” ......当一个函数被调用时，计算机必须‘记住’它是从，返回地址叫的地方，以便它可以返回到该位置，结果一旦通话已完成。通常情况下，这些信息会保存在堆栈中，按照它们描述的呼叫位置达到的时间顺序列出一个简单的返回位置列表。有时，函数在完成所有其他操作后所做的最后一件事情就是简单地调用一个函数，可能是它本身，然后返回结果。使用尾递归时，不需要记住我们正在调用的地方 - 相反，我们可以单独离开堆栈，而新调用的函数将直接返回原始调用者的结果。 在这种情况下将呼叫转换为分支或跳转称为尾部呼叫优化。请注意，在源代码中的所有其他语句之后，尾部调用不必出现在词法上;它只是重要的，其结果立即返回，因为调用函数将永远不会有机会做任何事情后，如果进行优化......“