什么是消除尾递归? [英] What is tail-recursion elimination?

问题描述

Steve Yegge在博客文章中提到了它，我不知道这是什么意思，有人可以填写我吗?

Steve Yegge mentioned it in a blog post and I have no idea what it means, could someone fill me in?

与尾部呼叫优化一样吗?

推荐答案

尾调用消除是一种节省堆栈空间的优化.它将功能呼叫替换为 goto .尾递归消除是一回事，但附加的约束是该函数正在调用自身.

Tail call elimination is an optimization that saves stack space. It replaces a function call with a goto. Tail recursion elimination is the same thing, but with the added constraint that the function is calling itself.

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

Basically, if the very last thing a function A does is return A(params...) then you can eliminate the allocation of a stack frame and instead set the appropriate registers and jump directly into the body of the function.

考虑(虚构的)调用约定，该约定将堆栈上的所有参数传递并返回某个寄存器中的值.

Consider an (imaginary) calling convention that passes all parameters on the stack and returns the value in some register.

某些功能可能会编译为(用虚构的汇编语言):

Some function could compile down to (in an imaginary assembly language):

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

无论上述内容实际做什么，每次调用函数都会占用一个全新的堆栈框架.但是，由于在尾部调用函数之后除了返回什么都没有发生，所以我们可以安全地优化这种情况.

Whatever the above actually does, it takes up a whole new stack frame for each call to function. However, since nothing occurs after the tail call to function except a return we can safely optimize that case away.

结果:

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

最终结果是一个等效函数，可节省大量堆栈空间，尤其是对于导致大量递归调用的输入而言.

The end result is an equivalent function that saves a lot of stack space, especially for inputs that result in a large number of recursive calls.

我的答案需要很多想象力，但我认为您可以理解.

There's a lot of imagination required in my answer, but I think you can get the idea.

这篇关于什么是消除尾递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！