什么是尾递归消除？

Question

Steve Yegge在一篇博客文章中提及它,我不知道这意味着什么,有人可以填写我吗？

它与尾部调用优化是一回事吗？

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

从这里:

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

来自维基百科:

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