跳到主要内容

C++ 递归

提示
  1. 递归的定义：在C++中，自己调用自己的函数称为递归函数，这种技术被称为递归。
  2. 递归的工作原理：递归函数通过不断调用自身来工作，直到满足某个条件，通常使用if...else语句或类似方法来避免无限递归。
  3. 递归的优缺点：递归使代码更短、更清晰，适用于数据结构和高级算法问题，但它占用更多的栈空间，使用更多处理器时间，并且可能比等效的迭代程序更难调试。

一个调用自身的函数被称为递归函数。这种技术称为递归。

C++ 中递归的工作原理​

void recurse()
{
 ... .. ...
 recurse();
 ... .. ...
}

int main()
{
 ... .. ...
 recurse();
 ... .. ...
}

下图显示了递归如何通过不断调用自身来工作。

C++ 递归的工作原理

递归会持续进行，直到满足某些条件。

为了防止无限递归，可以使用 if...else 语句（或类似方法），其中一个分支进行递归调用，另一个则不进行。

示例 1：使用递归计算数字的阶乘​

// n 的阶乘 = 1*2*3*...*n

#include <iostream>
using namespace std;

int factorial(int);

int main() {
 int n, result;

 cout << "输入一个非负数： ";
 cin >> n;

 result = factorial(n);
 cout << n << " 的阶乘 = " << result;
 return 0;
}

int factorial(int n) {
 if (n > 1) {
 return n * factorial(n - 1);
 } else {
 return 1;
 }
}

输出

输入一个非负数： 4
4 的阶乘 = 24

阶乘程序的工作原理​

C++ 递归程序的工作原理

如我们所见，factorial() 函数在调用自身。然而，在每次调用期间，我们都将 n 的值减少了 1。当 n 小于 1 时，factorial() 函数最终返回输出。

递归的优势和劣势​

以下是在 C++ 中使用递归的优缺点。

C++ 递归的优点​

  • 它使我们的代码更短、更清晰。
  • 在涉及数据结构和高级算法的问题中，如图和树遍历，递归是必需的。

C++ 递归的缺点​

  • 与迭代程序相比，它占用了更多的栈空间。
  • 它使用更多的处理器时间。
  • 与等效的迭代程序相比，它可能更难调试。
最后于 更新