第十九章：C++ 递归

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

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 << "阶乘 of " << n << " = " << result;
    return 0;
}

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

输出：

请输入一个非负数: 3
阶乘 of 3 = 6

上面程序中阶乘实现的工作流程

C++|递归程序是如何工作的

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

递归的优缺点

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

C++ 递归的优点

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

C++ 递归的缺点

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

程序算法实验室 zhangJA-Lab

转载请注明：XAMPP中文组官网 » 那些年C++ 函数之C++ 递归工作过程示意图