C++ 递归

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

C++中递归的工作原理

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

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

下图显示了递归是如何通过一遍又一遍地调用自身来工作的。

递归会一直调用自身直到满足某些条件后退出。

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

示例 1：使用递归对数字进行阶乘

// Factorial of n = 1*2*3*...*n

#include <iostream>
using namespace std;

int factorial(int);

int main() {
    int n, result;

    cout << "Enter a non-negative number: ";
    cin >> n;

    result = factorial(n);
    cout << "Factorial of " << n << " = " << result;
    return 0;
}

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

输出

Enter a non-negative number: 4
Factorial of 4 = 24

阶乘程序的工作原理

正如我们所见，该 factorial() 函数正在调用自身。但是，在每次调用期间，我们都将 n 的值减去 1 . 当 n 小于 1 的时候， factorial() 函数最终返回输出。

递归的优缺点

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

C++ 递归的优点

它使我们的代码更短、更干净。
涉及数据结构和高级算法的问题需要递归，例如图和树遍历。

C++ 递归的缺点

与迭代程序相比，它需要大量的堆栈空间。
它使用更多的处理器时间。
与等效的迭代程序相比，调试可能更加困难。