什么是尾递归消除？

发布于 2024-07-30 13:05:24 字数 274 浏览 7 评论 0原文

Steve Yegge 在博客文章中提到了这一点我不明白这是什么意思，有人可以帮我解答一下吗？

它与尾调用优化一样吗？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

奢华的一滴泪 2024-08-06 13:05:25

尾部调用消除是一种节省堆栈空间的优化。它将函数call替换为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

最终结果是一个等效的函数，可以节省大量堆栈空间，特别是对于导致大量递归调用的输入。

我的回答需要很多想象力，但我想你能明白我的意思。

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.

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.

Resulting in:

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.

回复收藏 0 原文

粉红×色少女 2024-08-06 13:05:25

来自此处：

"...尾递归消除是一个
尾调用消除的特殊情况
其中尾部调用是对
函数本身。在这种情况下
调用可以替换为跳转到
移动后开始功能
适当的新论据
寄存器或堆栈位置...”

来自维基百科：

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