如果有的话，C + + 编译器会执行尾部递归优化吗？

在我看来，在 C 和 C + + 中进行尾部递归优化完全可行，但在调试时，我似乎从未看到指示这种优化的框架堆栈。这很好，因为堆栈告诉我递归有多深。然而，这种优化也是不错的。

是否有任何 C + + 编译器做这种优化? 为什么? 为什么不？

我如何告诉编译器这样做呢？

  • 对于 MSVC: /O2或 /Ox
  • 对于海湾合作委员会: -O2或 -O3

如何检查编译器是否已经在某种情况下这样做？

  • 对于 MSVC，使 PDB 输出能够跟踪代码，然后检查代码
  • 海湾合作委员会... ？

对于如何确定某个函数是否被编译器像这样优化，我仍然需要一些建议(尽管我发现 Konrad 告诉我去假设它，这让我感到安心)

通过执行无限递归并检查它是否导致无限循环或堆栈溢出(我用 GCC 执行了这个操作，发现 -O2已经足够了) ，总是可以检查编译器是否完成了这项工作，但是我希望能够检查某个我知道无论如何都会终止的函数。我想有一个简单的方法来检查这个:)

经过一些测试后，我发现析构函数会破坏进行这种优化的可能性。有时候值得改变某些变量和临时变量的作用域，以确保它们在返回语句开始之前超出作用域。

如果在尾部调用之后需要运行任何析构函数，则不能执行尾部调用优化。

50101 次浏览
小开
最佳答案

所有当前的主流编译器都能很好地执行尾部调用优化(而且已经执行了十多年) ，即使是对于相互递归的调用如:

int bar(int, int);


int foo(int n, int acc) {
return (n == 0) ? acc : bar(n - 1, acc + 2);
}


int bar(int n, int acc) {
return (n == 0) ? acc : foo(n - 1, acc + 1);
}

让编译器进行优化很简单: 只要打开速度优化:

  • 对于 MSVC，使用 /O2或 /Ox。
  • 对于 GCC、 Clang 和 ICC，使用 -O3

检查编译器是否进行了优化的一个简单方法是执行一个调用，否则将导致堆栈溢出ーー或查看程序集输出。

作为一个有趣的历史记录，C 的尾部调用优化是由 Mark Probst 在 毕业论文过程中添加到 GCC 中的。本文描述了实现中的一些有趣的注意事项。值得一读。

小开

大多数编译器在调试构建中不进行任何类型的优化。

如果使用 VC，尝试开启 PDB 信息的发布版本-这将让你跟踪优化的应用程序，你应该有希望看到你想要什么。然而，请注意，调试和跟踪优化的构建将在各个地方跳来跳去，并且通常不能直接检查变量，因为它们只能在寄存器中结束，或者被完全优化。这是一次“有趣”的经历..。

小开

正如 Greg 提到的，编译器不会在调试模式下执行。调试构建比针对性构建慢是可以的，但是它们不应该更频繁地崩溃: 如果您依赖于尾部调用优化，它们可能正是这样做的。因此，最好将尾部调用重写为普通循环。:-(

小开

Gcc 4.3.2将这个函数(蹩脚/琐碎的 atoi()实现)完全内联到 main()中。优化级别为 -O1。我注意到如果我使用它(甚至将它从 static改为 extern，尾递归消失得很快，所以我不会依赖它来获得程序的正确性。

#include <stdio.h>
static int atoi(const char *str, int n)
{
if (str == 0 || *str == 0)
return n;
return atoi(str+1, n*10 + *str-'0');
}
int main(int argc, char **argv)
{
for (int i = 1; i != argc; ++i)
printf("%s -> %d\n", argv[i], atoi(argv[i], 0));
return 0;
}
小开

除了显而易见的(除非您要求，否则编译器不会进行这种优化) ，C + + 中的尾部调用优化还有一个复杂性: 析构函数。

比如:

   int fn(int j, int i)
{
if (i <= 0) return j;
Funky cls(j,i);
return fn(j, i-1);
}

编译器(通常)不能对此进行尾部调用优化，因为它需要 要调用 cls 之后的析构函数，递归调用返回。

有时编译器可以看到析构函数没有外部可见的副作用(因此可以提前完成) ，但通常不能。

其中一种特别常见的形式是 Funky实际上是 std::vector或类似的。


提交答案