有人可以向我展示一个简单的 C++ 尾递归函数吗？
为什么尾递归更好，如果它甚至更好？
除了尾递归还有哪些其他类型的递归？
问问题
44437 次
6 回答
65
一个简单的尾递归函数：
unsigned int f( unsigned int a ) {
if ( a == 0 ) {
return a;
}
return f( a - 1 ); // tail recursion
}
尾递归基本上是在：
- 只有一个递归调用
- 该调用是函数中的最后一条语句
它并不是“更好”，除非一个好的编译器可以删除递归，将其转换为循环。这可能会更快，并且肯定会节省堆栈使用量。GCC 编译器可以进行这种优化。
于 2010-04-22T19:09:47.497 回答
44
C++ 中的尾递归看起来与 C 或任何其他语言相同。
void countdown( int count ) {
if ( count ) return countdown( count - 1 );
}
尾递归（以及一般的尾调用）需要在执行尾调用之前清除调用者的堆栈帧。对于程序员来说，尾递归类似于循环，return简化为goto first_line;. 但是，编译器需要检测你在做什么，如果没有，仍然会有一个额外的堆栈帧。大多数编译器都支持它，但编写循环或goto通常更容易且风险更小。
非递归尾调用可以启用随机分支（就像goto其他函数的第一行一样），这是一个更独特的工具。
return请注意，在 C++ 中，语句范围内不能有任何具有非平凡析构函数的对象。函数结束清理将要求被调用者返回给调用者，从而消除尾调用。
还要注意（在任何语言中）尾递归需要在每一步通过函数参数列表传递算法的整个状态。（这从函数的堆栈帧在下一次调用开始之前被消除的要求中很明显......你不能将任何数据保存在局部变量中。）此外，在函数的返回值被尾部返回之前，不能对函数的返回值应用任何操作.
int factorial( int n, int acc = 1 ) {
if ( n == 0 ) return acc;
else return factorial( n-1, acc * n );
}
于 2010-04-22T19:13:17.393 回答
28
尾递归是尾调用的一种特殊情况。尾调用是编译器可以看到在从被调用函数返回时不需要执行任何操作的地方——本质上是将被调用函数的返回变成它自己的。编译器通常可以做一些堆栈修复操作，然后跳转（而不是调用）到被调用函数的第一条指令的地址。
除了消除一些返回调用之外，这样做的好处之一是您还减少了堆栈的使用。在某些平台或操作系统代码中，堆栈可能非常有限，而在高级机器上，如我们桌面中的 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);
}
z 在这里从 qwerty 返回后可能必须被破坏。
另一件事是隐式类型转换，这也可能发生在 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 将返回对自身的引用（这就是为什么您可以将很多东西串在一起以 << 分隔的列表中），然后您强制将其评估为布尔值，最终调用 cout 的另一个方法 operator bool( ）。在这种情况下，这个 cout.operator bool() 可以作为尾调用调用，但 operator<< 不能。
编辑：
值得一提的是，在 C 语言中进行尾调用优化的一个主要原因是编译器知道被调用函数会将其返回值存储在与调用函数必须确保其返回值相同的位置。存储在。
于 2010-04-22T19:57:52.133 回答
2
尾递归实际上是同时处理两个问题的技巧。第一个是在很难知道要执行的迭代次数时执行循环。
虽然这可以通过简单的递归来解决，但出现了第二个问题，即由于递归调用执行次数过多而导致堆栈溢出。当伴随“计算和携带”技术时，尾调用是解决方案。
在基础 CS 中，您会了解到计算机算法需要具有不变量和终止条件。这是构建尾递归的基础。
- 所有计算都发生在参数传递中。
- 所有结果都必须传递给函数调用。
- 尾调用是最后一个调用，发生在终止时。
简单地说，你的函数的返回值不能进行任何计算。
以计算 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 次方。
大多数编译器都有嵌套调用的限制，因此尾调用技巧会有所帮助。显然，没有元编程循环，所以必须使用递归。
于 2015-11-30T02:32:35.620 回答
1
在 C++ 的编译器级别，尾递归实际上并不存在。
尽管您可以编写使用尾递归的程序，但您无法获得通过支持编译器/解释器/语言实现的尾递归的继承优势。例如，Scheme 支持尾递归优化，因此它基本上会将递归变为迭代。这使得堆栈溢出更快且无懈可击。C++ 没有这样的东西。（至少没有我见过的任何编译器）
显然，MSVC++ 和 GCC 中都存在尾递归优化。有关详细信息，请参阅此问题。
于 2010-04-22T19:13:23.157 回答
0
维基百科有一篇关于尾递归的不错的文章。基本上，尾递归优于常规递归，因为将其优化为迭代循环很简单，并且迭代循环通常比递归函数调用更有效。这在没有循环的函数式语言中尤为重要。
对于 C++，如果您可以使用尾递归编写递归循环仍然很好，因为它们可以得到更好的优化，但在这种情况下，您通常可以一开始就迭代地进行，因此收益不如它会那么大使用功能语言。
于 2010-04-22T19:16:17.673 回答