C++ 中的尾递归

Question

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

如果尾递归更好的话，为什么它更好呢？

除了尾递归之外，还有哪些递归？

Answer 1

一个简单的尾递归函数：

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

尾递归基本上是这样的：

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

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

Answer 2

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

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

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

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

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

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

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

Answer 3

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

除了消除一些返回调用之外，这样做的一大好处是您还可以减少堆栈的使用。在某些平台或操作系统代码中，堆栈可能非常有限，并且在高级计算机（例如台式机中的 x86 CPU）上，像这样减少堆栈使用将提高数据缓存性能。

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

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

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

这很简单，许多编译器可能无论如何都能弄清楚，但正如您所看到的，需要添加一个内容发生在被调用的 sum 返回一个数字之后，因此简单的尾部调用优化是不可能的。

如果您这样做：

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

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

既然您在问题中提到了 C++，我将提到一些与此相关的特殊内容。
C++ 向您隐藏了一些 C 不会的东西。这些析构函数是阻碍尾部调用优化的主要因素。

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

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

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

这里从qwerty返回后可能必须破坏z。

另一件事是隐式类型转换，这也可能发生在 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);
}

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

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

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

这里有一个对 cout.operator<< 的调用作为最后的陈述。 cout 将返回对其自身的引用（这就是为什么您可以将很多东西串在一起在一个由 << 分隔的列表中），然后强制将其计算为 bool，这最终会调用 cout 的另一个方法，运算符布尔（）。在这种情况下，这个 cout.operator bool() 可以作为尾调用来调用，但是operator<<不能。

编辑：

值得一提的是，C 中尾调用优化成为可能的一个主要原因是编译器知道被调用函数将其返回值存储在与调用函数必须确保其返回值相同的位置值存储在.

Answer 4

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

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

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

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

简而言之，函数的返回值不得进行任何计算。

以计算 10 的幂为例，这很简单，可以用循环编写。

应该看起来像

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

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

ret,p,res

-,4,1

-,3,10

-,2,100

-,1,1000

-,0,10000

10000,-,-

很明显，编译器只需在不更改堆栈指针的情况下以及发生尾调用时复制值即可只是为了返回结果。

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

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

};

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

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

Answer 5

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

虽然您可以编写使用尾递归的程序，但您无法获得通过支持编译器/解释器/语言实现的尾递归的继承优势。例如Scheme支持尾递归优化，这样它基本上就会将递归变成迭代。这使得它更快并且不易发生堆栈溢出。 C++没有这样的东西。 （至少我见过的任何编译器都没有）

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

Answer 6

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

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