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

Question

史蒂夫·耶格(Steve Yegge)在blog post中提到了它，我不知道这是什么意思，有人可以帮我吗？

和tail call optimization是一样的东西吗？

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

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

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