language-agnostic - 什么是尾递归消除？

Question

Steve Yegge 在一篇博文中提到了它，我不知道它是什么意思，有人能补充一下吗？

它与尾调用优化相同吗？

Answer 1

尾调用消除是一种节省堆栈空间的优化。它用goto替换函数调用。尾递归消除是同样的事情，但增加了函数调用自身的约束。

基本上，如果函数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

从这里：

“...尾递归消除是尾调用消除的一种特殊情况，其中尾调用是对函数本身的调用。在这种情况下，可以在移动新参数后将调用替换为跳转到函数的开头到适当的寄存器或堆栈位置..."

来自维基百科：

“......当一个函数被调用时，计算机必须“记住”它被调用的地方，返回地址，这样一旦调用完成，它就可以带着结果返回到那个位置。通常，这些信息会被保存在堆栈上，一个简单的返回位置列表，按照它们描述的调用位置到达的时间顺序排列。有时，一个函数在完成所有其他操作后做的最后一件事就是简单地调用一个函数，可能是它自己，然后返回它的结果。使用尾递归，不需要记住我们调用的位置——相反，我们可以不理会堆栈，新调用的函数将直接将其结果返回给原始调用者。将调用转换为分支在这种情况下或跳转称为尾调用优化。请注意，尾调用不必在源代码中的所有其他语句之后出现在词法上；唯一重要的是立即返回其结果，因为如果执行优化，调用函数将永远不会有机会在调用后做任何事情......"