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通常更容易且风险更小.

非递归尾调用可以启用随机分支(比如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++隐藏了一些你不喜欢的东西.这些析构函数中的主要因素是尾部调用优化.

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的方法,operator bool( ).在这种情况下,这个cout.operator bool()可以被称为尾调用,但是运算符<<不能.

编辑:

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