为什么尾部调用优化需要垃圾收集？

Question

为什么尾调用优化需要垃圾收集？ 是否因为如果您在一个函数中分配内存，然后想要对其进行尾部调用，则无法进行尾部调用并重新获得该内存？ （因此必须保存堆栈，以便在尾部调用之后可以回收内存。）

Answer 1

像大多数神话一样，这个神话可能有一定道理。 虽然尾部调用优化不需要 GC，但在某些情况下它确实有帮助。 假设您在 C++ 中有类似的内容：

int foo(int arg) {
    // Base case.

    vector<double> bar(10);
    // Populate bar, do other stuff.

    return foo(someNumber);
}

在本例中，return foo(someNumber); 看起来像尾部调用，但因为您使用的是 RAII 内存管理，并且必须释放内存条，所以该行将转换为较低级别，如下所示（非正式伪代码）：

ret = foo(someNumber);
free(bar);
return ret;

如果您有 GC ，编译器没有必要向空闲栏插入指令。 因此，这个函数可以优化为尾调用。

Answer 2

你是从哪里听来的？

即使没有任何类型的垃圾收集器的 C 编译器也能够优化对其迭代等效项的尾递归调用。

Answer 3

尾部调用优化不需要垃圾收集。

调用堆栈上分配的任何变量都将在递归调用中重用，因此不会出现内存泄漏。

无论是否使用尾调用优化，在堆上分配且在尾调用之前未释放的任何局部变量都会泄漏内存。 无论是否使用尾调用优化，在堆上分配并在尾调用之前释放的局部变量都不会泄漏内存。

Answer 4

确实，尾部调用优化并不真正需要垃圾收集。

然而，假设您有 1 GB 的 RAM，并且您想要过滤 900MB 的整数列表以仅保留正数。 假设大约一半是积极的，一半是消极的。

在具有 GC 的语言中，您只需编写函数即可。 GC 会发生很多次，最终会得到一个 450 MB 的列表。 代码将如下所示：

list *result = filter(make900MBlist(), funcptr);

make900MBlist 将逐渐被 GCd，因为已完成的部分过滤器不再被任何内容引用。

在没有 GC 的语言中，为了保留尾递归，您必须执行以下操作：

list *srclist = make900MBlist();
list *result = filter(srclist, funcptr);
freelist(srclist);

在最终释放 srclist 之前，最终必须使用 900MB + 450MB，因此程序将耗尽内存并失败。

如果您编写自己的filter_reclaim，则会释放输入列表，因为它不再需要：

list *result = filter_reclaim(make900MBlist(), funcptr);

它将不再是尾递归，并且您可能会溢出堆栈。