C++ 递归
提示
- 递归的定义:在C++中,自己调用自己的函数称为递归函数,这种技术被称为递归。
- 递归的工作原理:递归函数通过不断调用自身来工作,直到满足某个条件,通常使用
if...else
语句或类似方法来避免无限递归。 - 递归的优缺点:递归使代码更短、更清晰,适用于数据结构和高级算法问题,但它占用更多的栈空间,使用更多处理器时间,并且可能比等效的迭代程序更难调试。
一个调用自身的函数被称为递归函数。这种技术称为递归。
C++ 中递归的工作原理
void recurse()
{
... .. ...
recurse();
... .. ...
}
int main()
{
... .. ...
recurse();
... .. ...
}
下图显示了递归如何通过不断调用自身来工作。
递归会持续进行,直到满足某些条件。
为了防止无限递归,可以使用 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
阶乘程序的工作原理
如我们所见,factorial()
函数在调用自身。然而,在每次调用期间,我们都将 n 的值减少了 1
。当 n 小于 1
时,factorial()
函数最终返回输出。
递归的优势和劣势
以下是在 C++ 中使用递归的优缺点。
C++ 递归的优点
- 它使我们的代码更短、更清晰。
- 在涉及数据结构和高级算法的问题中,如图和树遍历,递归是必需的。
C++ 递归的缺点
- 与迭代程序相比,它占用了更多的栈空间。
- 它使用更多的处理器时间。
- 与等效的迭代程序相比,它可能更难调试。