数据结构中的尾递归

我们将在本文中了解什么是尾递归。尾递归基本上是使用递归函数作为函数的最后一条语句。因此，当完成递归调用后无所事事，即称为尾递归。我们来看一个尾递归的示例。

示例

 现场演示

#include <iostream>
using namespace std;
void printN(int n){
   if(n < 0){
      return;
   }
   cout << n << " ";
   printN(n - 1);
}
int main() {
   printN(10);
}

输出

10 9 8 7 6 5 4 3 2 1 0

尾递归比非尾递归更好。由于在递归调用后没有剩余任务，因此编译器可以更轻松地优化代码。调用一个函数时，其地址将存储在堆栈中。因此，如果它是尾递归，则无需将地址存储到堆栈中。

我们可以使用递归来计算阶乘，但该函数不是尾递归。在 fact(n) 中使用了 fact(n-1) 的值。

long fact(int n){
   if(n <= 1)
      return 1;
   n * fact(n-1);
}

我们可以通过添加一些其他参数来使其成为尾递归。如下所示：

long fact(long n, long a){
   if(n == 0)
      return a;
   return fact(n-1, a*n);
}

阿纳布·查克拉巴蒂

更新于：2019 年 8 月 27 日

4K+ 次查看

开启你的 职业生涯

完成课程以获得认证

开始