1

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

4

4 回答 4

9

像大多数神话一样，这个神话可能有一定的道理。虽然尾调用优化不需要GC ，但它在某些情况下肯定会有所帮助。假设你在 C++ 中有这样的东西：

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

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

    return foo(someNumber);
}

在这种情况下，返回 foo(someNumber); 看起来像一个尾调用，但是因为您使用的是 RAII 内存管理，并且您必须释放 bar，所以此行将转换为较低级别，如下所示（在非正式伪代码中）：

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

如果你有 GC，编译器就不需要插入指令来释放 bar。因此，这个函数可以优化为尾调用。

于 2008-12-12T18:27:51.500 回答
7

你是从哪里听来的？

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

于 2008-12-05T17:27:33.023 回答
4

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

在调用堆栈上分配的任何变量都将在递归调用中重用，因此那里没有内存泄漏。

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

于 2008-12-05T17:39:54.497 回答
2

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

但是，假设您有 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);

它不再是尾递归的，你可能会溢出你的堆栈。

于 2008-12-06T20:53:16.307 回答