哪些（如果有）C++ 编译器进行尾递归优化？

Which, if any, C++ compilers do tail-recursion optimization?

提问by Magnus Hoff

It seems to me that it would work perfectly well to do tail-recursion optimization in both C and C++, yet while debugging I never seem to see a frame stack that indicates this optimization. That is kind of good, because the stack tells me how deep the recursion is. However, the optimization would be kind of nice as well.

在我看来，在 C 和 C++ 中进行尾递归优化都可以很好地工作，但是在调试时我似乎从未看到指示这种优化的帧堆栈。这很好，因为堆栈告诉我递归有多深。但是，优化也会很好。

Do any C++ compilers do this optimization? Why? Why not?

有没有 C++ 编译器做这个优化？为什么？为什么不？

How do I go about telling the compiler to do it?

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

• For MSVC: /O2or /Ox
• For GCC: -O2or -O3

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

How about checking if the compiler has done this in a certain case?

在某种情况下，如何检查编译器是否已完成此操作？

• For MSVC, enable PDB output to be able to trace the code, then inspect the code
• For GCC..?

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

I'd still take suggestions for how to determine if a certain function is optimized like this by the compiler (even though I find it reassuring that Konrad tells me to assume it)

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

It is always possible to check if the compiler does this at all by making an infinite recursion and checking if it results in an infinite loop or a stack overflow (I did this with GCC and found out that -O2is sufficient), but I want to be able to check a certain function that I know will terminate anyway. I'd love to have an easy way of checking this :)

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

---

---

After some testing, I discovered that destructors ruin the possibility of making this optimization. It can sometimes be worth it to change the scoping of certain variables and temporaries to make sure they go out of scope before the return-statement starts.

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

If any destructor needs to be run after the tail-call, the tail-call optimization can not be done.

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

采纳答案by Konrad Rudolph

All current mainstream compilers perform tail call optimisationfairly well (and have done for more than a decade), even for mutually recursive callssuch as:

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

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);
}

Letting the compiler do the optimisation is straightforward: Just switch on optimisation for speed:

让编译器进行优化很简单：只需打开优化以提高速度：

• For MSVC, use /O2or /Ox.
• For GCC, Clang and ICC, use -O3

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

An easy way to check if the compiler did the optimisation is to perform a call that would otherwise result in a stack overflow — or looking at the assembly output.

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

As an interesting historical note, tail call optimisation for C was added to the GCC in the course of a diploma thesisby Mark Probst. The thesis describes some interesting caveats in the implementation. It's worth reading.

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

回答by Tom Barta

gcc 4.3.2 completely inlines this function (crappy/trivial atoi()implementation) into main(). Optimization level is -O1. I notice if I play around with it (even changing it from staticto extern, the tail recursion goes away pretty fast, so I wouldn't depend on it for program correctness.

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;
}

回答by Martin Bonner supports Monica

As well as the obvious (compilers don't do this sort of optimization unless you ask for it), there is a complexity about tail-call optimization in C++: destructors.

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

Given something like:

给出类似的东西：

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

The compiler can't (in general) tail-call optimize this because it needs to call the destructor of clsafterthe recursive call returns.

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

Sometimes the compiler can see that the destructor has no externally visible side effects (so it can be done early), but often it can't.

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

A particularly common form of this is where Funkyis actually a std::vectoror similar.

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

回答by Greg Whitfield

Most compilers don't do any kind of optimisation in a debug build.

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

If using VC, try a release build with PDB info turned on - this will let you trace through the optimised app and you should hopefully see what you want then. Note, however, that debugging and tracing an optimised build will jump you around all over the place, and often you cannot inspect variables directly as they only ever end up in registers or get optimised away entirely. It's an "interesting" experience...

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

回答by 0124816

As Greg mentions, compilers won't do it in debug mode. It's ok for debug builds to be slower than a prod build, but they shouldn't crash more often: and if you depend on a tail call optimization, they may do exactly that. Because of this it is often best to rewrite the tail call as an normal loop. :-(

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