C++中的尾递归

Tail recursion in C++

提问by neuromancer

Can someone show me a simple tail-recursive function in C++?

有人可以用 C++ 向我展示一个简单的尾递归函数吗？

Why is tail recursion better, if it even is?

为什么尾递归更好，如果甚至更好？

What other kinds of recursion are there besides tail recursion?

除了尾递归，还有哪些递归呢？

采纳答案by neuromancer

A simple tail recursive function:

一个简单的尾递归函数：

unsigned int f( unsigned int a ) {
   if ( a == 0 ) {
      return a;
   }
   return f( a - 1 );   // tail recursion
}

Tail recursion is basically when:

尾递归基本上是在以下情况下：

• there is only a single recursive call
• that call is the last statement in the function

• 只有一个递归调用
• 该调用是函数中的最后一条语句

And it's not "better", except in the sense that a good compiler can remove the recursion, transforming it into a loop. This may be faster and will certainly save on stack usage. The GCC compiler can do this optimisation.

而且它并不是“更好”，除非一个好的编译器可以删除递归，将其转换为循环。这可能会更快，并且肯定会节省堆栈使用量。GCC 编译器可以进行这种优化。

回答by Potatoswatter

Tail recusion in C++ looks the same as C or any other language.

C++ 中的尾部回避看起来与 C 或任何其他语言相同。

void countdown( int count ) {
    if ( count ) return countdown( count - 1 );
}

Tail recursion (and tail calling in general) requires clearing the caller's stack frame before executing the tail call. To the programmer, tail recursion is similar to a loop, with returnreduced to working like goto first_line;. The compiler needs to detect what you are doing, though, and if it doesn't, there will still be an additional stack frame. Most compilers support it, but writing a loop or gotois usually easier and less risky.

尾递归（以及一般的尾调用）需要在执行尾调用之前清除调用者的堆栈帧。对于程序员来说，尾递归类似于循环，return简化为像goto first_line;. 但是，编译器需要检测您在做什么，如果没有，仍然会有一个额外的堆栈帧。大多数编译器都支持它，但编写循环或goto通常更容易且风险更小。

Non-recursive tail calls can enable random branching (like gototo the first line of some other function), which is a more unique facility.

非递归尾调用可以启用随机分支（如goto某些其他函数的第一行），这是一种更独特的功能。

Note that in C++, there cannot be any object with a nontrivial destructor in the scope of the returnstatement. The end-of-function cleanup would require the callee to return back to the caller, eliminating the tail call.

请注意，在 C++ 中，return语句范围内不能有任何具有非平凡析构函数的对象。函数结束清理将要求被调用者返回给调用者，从而消除尾调用。

Also note (in any language) that tail recursion requires the entire state of the algorithm to be passed through the function argument list at each step. (This is clear from the requirement that the function's stack frame be eliminated before the next call begins… you can't be saving any data in local variables.) Furthermore, no operation can be applied to the function's return value before it's tail-returned.

还要注意（在任何语言中）尾递归需要在每一步通过函数参数列表传递算法的整个状态。（这从在下一次调用开始之前消除函数的堆栈帧的要求中可以清楚地看出……您不能将任何数据保存在局部变量中。）此外，在尾部返回之前不能对函数的返回值应用任何操作.

int factorial( int n, int acc = 1 ) {
    if ( n == 0 ) return acc;
    else return factorial( n-1, acc * n );
}

回答by nategoose

Tail recursion is a special case of a tail call. A tail call is where the compiler can see that there are no operations that need to be done upon return from a called function -- essentially turning the called function's return into it's own. The compiler can often do a few stack fix-up operations and then jump (rather than call) to the address of the first instruction of the called function.

尾递归是尾调用的特例。尾调用是编译器可以看到从被调用函数返回时不需要执行任何操作的地方——本质上是将被调用函数的返回转换为它自己的返回。编译器通常可以做一些堆栈修复操作，然后跳转（而不是调用）到被调用函数的第一条指令的地址。

One of the great things about this besides eliminating some return calls is that you also cut down on stack usage. On some platforms or in OS code the stack can be quite limited and on advanced machines like the x86 CPUs in our desktops decreasing the stack usage like this will improve data cache performance.

除了消除一些返回调用之外，这样做的好处之一是您还减少了堆栈使用。在某些平台或操作系统代码中，堆栈可能非常有限，而在我们台式机中的 x86 CPU 等高级机器上，像这样减少堆栈使用量将提高数据缓存性能。

Tail recursion is where the called function is the same as the calling function. This can be turned into loops, which is exactly the same as the jump in the tail call optimization mentioned above. Since this is the same function (callee and caller) there are fewer stack fixups that need to be done before the jump.

尾递归是被调用函数与调用函数相同的地方。这可以变成循环，和上面提到的尾调用优化中的跳转完全一样。由于这是同一个函数（被调用者和调用者），因此在跳转之前需要完成的堆栈修复更少。

The following shows a common way to do a recursive call which would be more difficult for a compiler to turn into a loop:

下面显示了执行递归调用的常见方法，这对于编译器来说更难变成循环：

int sum(int a[], unsigned len) {
     if (len==0) {
         return 0;
     }
     return a[0] + sum(a+1,len-1);
}

This is simple enough that many compilers could probably figure it out anyway, but as you can see there is an addition that needs to happen after the return from the called sum returns a number, so a simple tail call optimization is not possible.

这很简单，以至于许多编译器无论如何都可能弄清楚，但是正如您所看到的，在从被调用的 sum 返回一个数字之后需要进行一个加法，因此不可能进行简单的尾调用优化。

If you did:

如果你这样做：

static int sum_helper(int acc, unsigned len, int a[]) {
     if (len == 0) {
        return acc;
     }
     return sum_helper(acc+a[0], len-1, a+1);
}
int sum(int a[], unsigned len) {
     return sum_helper(0, len, a);
}

You would be able to take advantage of the calls in both functions being tail calls. Here the sum function's main job is to move a value and clear a register or stack position. The sum_helper does all of the math.

您将能够利用作为尾调用的两个函数中的调用。这里 sum 函数的主要工作是移动一个值并清除寄存器或堆栈位置。sum_helper 完成所有数学运算。

Since you mentioned C++ in your question I'll mention some special things about that. C++ hides some things from you which C does not. Of these destructors are the main thing that will get in the way of tail call optimization.

既然你在问题中提到了 C++，我会提到一些关于它的特殊事情。C++ 对你隐藏了一些 C 没有的东西。在这些析构函数中，主要是会妨碍尾调用优化。

int boo(yin * x, yang *y) {
    dharma z = x->foo() + y->bar();
    return z.baz();
}

In this example the call to baz is not really a tail call because z needs to be destructed after the return from baz. I believe that the rules of C++ may make the optimization more difficult even in cases where the variable is not needed for the duration of the call, such as:

在这个例子中，对 baz 的调用并不是真正的尾调用，因为 z 需要在从 baz 返回后被销毁。我相信即使在调用期间不需要变量的情况下，C++ 的规则也可能使优化变得更加困难，例如：

int boo(yin * x, yang *y) {
    dharma z = x->foo() + y->bar();
    int u = z.baz();
    return qwerty(u);
}

z may have to be destructed after the return from qwerty here.

z 可能必须在从 qwerty 返回后销毁。

Another thing would be implicit type conversion, which can happen in C as well, but can more complicated and common in C++. For instance:

另一件事是隐式类型转换，这在 C 中也可能发生，但在 C++ 中可能更复杂和常见。例如：

static double sum_helper(double acc, unsigned len, double a[]) {
     if (len == 0) {
        return acc;
     }
     return sum_helper(acc+a[0], len-1, a+1);
}
int sum(double a[], unsigned len) {
     return sum_helper(0.0, len, a);
}

Here sum's call to sum_helper is not a tail call because sum_helper returns a double and sum will need to convert that into an int.

这里 sum 对 sum_helper 的调用不是尾调用，因为 sum_helper 返回一个 double 并且 sum 需要将它转换为一个 int。

In C++ it is quite common to return an object reference which may have all kinds of different interpretations, each of which could be a different type conversion, For instance:

在 C++ 中，返回一个可能有各种不同解释的对象引用是很常见的，每个解释都可能是不同的类型转换，例如：

bool write_it(int it) {
      return cout << it;
}

Here there is a call made to cout.operator<< as the last statement. cout will return a reference to itself (which is why you can string lots of things together in a list separated by << ), which you then force to be evaluated as a bool, which ends up calling another of cout's methods, operator bool(). This cout.operator bool() could be called as a tail call in this case, but operator<< could not.

这里调用了 cout.operator<< 作为最后一条语句。cout 将返回对自身的引用（这就是为什么您可以将很多东西串在一个由 << 分隔的列表中），然后您强制将其评估为 bool，最终调用 cout 的另一个方法 operator bool( ）。在这种情况下，这个 cout.operator bool() 可以被称为尾调用，但 operator<< 不能。

EDIT:

编辑：

One thing that is worth mentioning is that a major reason that tail call optimization in C is possible is that the compiler knows that the called function will store it's return value in the same place as the calling function would have to ensure that its return value is stored in.

值得一提的是，在 C 中进行尾调用优化的一个主要原因是编译器知道被调用函数会将其返回值存储在调用函数必须确保其返回值是存储在。

回答by g24l

Tail recursion is a trick to actually cope with two issues at the same time. The first is executing a loop when it is hard to know the number of iterations to do.

尾递归是一种同时实际处理两个问题的技巧。第一种是在难以知道要执行的迭代次数时执行循环。

Though this can be worked out with simple recursion, the second problem arises which is that of stack overflow due to the recursive call being executed too many times. The tail call is the solution, when accompanied by a "compute and carry" technique.

虽然这可以通过简单的递归来解决，但出现了第二个问题，即由于递归调用执行次数过多而导致堆栈溢出。当伴随着“计算和携带”技术时，尾调用是解决方案。

In basic CS you learn that a computer algorithm needs to have an invariant and a termination condition. This is the base for building the tail recursion.

在基本的 CS 中，您将了解到计算机算法需要具有不变量和终止条件。这是构建尾递归的基础。

1. All computation happens in the argument passing.
2. All results must be passed onto function calls.
3. The tail call is the last call, and occurs at termination.

1. 所有计算都发生在参数传递中。
2. 所有结果都必须传递给函数调用。
3. 尾调用是最后一个调用，发生在终止时。

To simply put it, no computation must happen on the return value of your function.

简单地说，您的函数的返回值不必进行任何计算。

Take for example the computation of a power of 10, which is trivial and can be written by a loop.

以 10 的幂的计算为例，这是微不足道的，可以用循环编写。

Should look something like

应该看起来像

template<typename T> T pow10(T const p, T const res =1)
{
return p ? res: pow10(--p,10*res);
}

This gives an execution, e.g 4:

这给出了一个执行，例如 4：

ret,p,res

ret,p,res

-,4,1

-,3,10

-,2,100

-,1,1000

-,0,10000

10000,-,-

-,4,1

-,3,10

-,2,100

-,1,1000

-,0,10000

10000,-,-

It is clear that the compiler just has to copy values without changing the stack pointer and when the tail call happens just to return the result.

很明显，编译器只需要在不改变堆栈指针的情况下复制值，并且当尾调用发生时只需要返回结果。

Tail recursion is very important because it can provide ready made compile time evaluations, e.g. The above can be made to be.

尾递归非常重要，因为它可以提供现成的编译时评估，例如上面的可以成为。

template<int N,int R=1> struct powc10
{
int operator()() const
{
return  powc10<N-1, 10*R>()();
}
};

template<int R> struct powc10<0,R>
{

int operator()() const
{
return  R;
}

};

this can be used as powc10<10>()()to compute the 10th power at compile time.

这可用于powc10<10>()()在编译时计算 10 次方。

Most compilers have a limit of nested calls so the tail call trick helps. Evidently,there are no meta programming loops, so have to use recursion.

大多数编译器都有嵌套调用的限制，因此尾调用技巧会有所帮助。显然，没有元编程循环，所以必须使用递归。

回答by Earlz

Tail recursion does not exist really at compiler level in C++.

尾递归在 C++ 的编译器级别实际上并不存在。

Although you can write programs that use tail recursion, you do not get the inherit benefits of tail recursion implemented by supporting compilers/interpreters/languages. For instance Scheme supports a tail recursion optimization so that it basically will change recursion into iteration. This makes it faster and invulnerable to stack overflows. C++ does not have such a thing. (least not any compiler I've seen)

尽管您可以编写使用尾递归的程序，但您无法获得尾递归的继承优势，这些优势是通过支持编译器/解释器/语言实现的。例如 Scheme 支持尾递归优化，因此它基本上将递归变为迭代。这使得堆栈溢出更快且无懈可击。C++ 没有这样的东西。（至少没有我见过的任何编译器）

Apparently tail recursion optimizations exist in both MSVC++ and GCC. See this questionfor details.

显然，尾递归优化存在于 MSVC++ 和 GCC 中。有关详细信息，请参阅此问题。

回答by Jonathan M Davis

Wikipedia has a decent article on tail recursion. Basically, tail recursion is better than regular recursion because it's trivial to optimize it into an iterative loop, and iterative loops are generally more efficient than recursive function calls. This is particularly important in functional languages where you don't have loops.

维基百科有一篇关于尾递归的不错的文章。基本上，尾递归比常规递归更好，因为将其优化为迭代循环是微不足道的，并且迭代循环通常比递归函数调用更有效。这在没有循环的函数式语言中尤为重要。

For C++, it's still good if you can write your recursive loops with tail recursion since they can be better optimized, but in such cases, you can generally just do it iteratively in the first place, so the gain is not as great as it would be in a functional language.

对于 C++，如果您可以使用尾递归编写递归循环仍然很好，因为它们可以得到更好的优化，但是在这种情况下，您通常可以首先迭代地执行它，因此增益没有它那么大使用函数式语言。