recursion - 尾递归支持可以缩短其他函数调用的堆栈吗？

Question

支持尾递归的语言可以将相同的技术应用于非递归函数调用吗？

例如，如果该函数foo所做的最后一件事是返回调用的值bar，那么该语言是否会丢弃foo的堆栈帧？是否有任何已知的语言实际上可以做到这一点？

Answer 1

二郎做：

此处看到的尾递归不会使内存增长，因为当虚拟机看到一个函数在尾部位置（函数中要计算的最后一个表达式）调用自身时，它会消除当前的堆栈帧。这称为尾调用优化 (TCO)，它是一种更通用的优化的特例，称为最后调用优化 (LCO)。

只要函数体中要计算的最后一个表达式是另一个函数调用，就会执行 LCO。当这种情况发生时，与 TCO 一样，Erlang VM 会避免存储堆栈帧。因此，在多个函数之间也可以进行尾递归。例如，函数链 a() -> b()。b() -> c()。c() -> a()。将有效地创建一个不会耗尽内存的无限循环，因为 LCO 避免了堆栈溢出。这个原则，结合我们对累加器的使用，使尾递归变得有用。

Answer 2

是的，它可以。例如，考虑以下 C 代码：

int f();
int g() { return f(); }

当我使用gcc 4.6.3with -O3on编译它时x86-64，我得到以下程序集g()：

g:
        xorl    %eax, %eax
        jmp     f              ; <==== unconditional jump to f