160

在我看来，在 C 和 C++ 中进行尾递归优化会非常好，但是在调试时，我似乎从来没有看到表明这种优化的帧堆栈。这很好，因为堆栈告诉我递归有多深。但是，优化也会很好。

是否有任何 C++ 编译器进行此优化？为什么？为什么不？

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

  • 对于 MSVC：/O2或/Ox
  • 对于 GCC：-O2或-O3

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

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

我仍然会就如何确定编译器是否像这样优化某个函数提出建议（尽管我发现康拉德告诉我假设它令人放心）

总是可以通过进行无限递归并检查它是否导致无限循环或堆栈溢出来检查编译器是否完全执行此操作（我使用 GCC 执行此操作并发现这就-O2足够了），但我想成为能够检查我知道无论如何都会终止的某个功能。我很想有一个简单的方法来检查这个:)

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

如果在尾调用之后需要运行任何析构函数，则无法进行尾调用优化。

4

5 回答 5

139

当前所有主流编译器都可以很好地执行尾调用优化（并且已经做了十多年），即使对于相互递归的调用，例如：

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

检查编译器是否进行了优化的一种简单方法是执行一个调用，否则会导致堆栈溢出——或者查看汇编输出。

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

于 2008-08-29T07:40:32.280 回答
21

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;
}
于 2008-10-21T03:13:20.523 回答
21

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

给定类似的东西：

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

编译器不能（通常）尾调用优化它，因为它需要在递归调用返回cls 后调用析构函数。

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

一个特别常见的形式是 whereFunky实际上是 astd::vector或类似的。

于 2016-02-26T10:28:46.927 回答
11

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

如果使用 VC，请尝试打开 PDB 信息的发布版本 - 这将让您跟踪优化的应用程序，然后您应该希望看到您想要的。但是请注意，调试和跟踪优化的构建会让你到处乱跑，而且通常你不能直接检查变量，因为它们只会出现在寄存器中或完全被优化掉。这是一次“有趣”的经历……

于 2008-08-29T07:48:26.940 回答
7

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

于 2008-09-16T10:42:07.840 回答