数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学数据结构中的递归原理
递归是一个函数调用自身的进程。我们使用递归将更大的问题分解成更小的子问题。需要注意的是，只有当每个子问题都遵循相同类型的模式时，我们才能使用递归方法。
一个递归函数有两个不同的部分：基本情况和递归情况。基本情况用于终止递归任务。如果未定义基本情况，则函数将无限次递归（理论上）。
在计算机程序中，当我们调用一个函数时，程序计数器的值会在跳转到函数区域之前存储到内部堆栈中。完成任务后，它会弹出地址并将其分配给程序计数器，然后恢复任务。在递归调用期间，它会多次存储地址，并跳转到下一个函数调用语句。如果未定义基本情况，它将反复递归，并将地址存储到堆栈中。如果堆栈没有更多空间，它将引发“内部堆栈溢出”错误。
递归调用的一个例子是查找一个数字的阶乘。我们可以看到，一个数 n 的阶乘 n! 等于 n * (n-1)!，又等于 n * (n - 1) * (n - 2)!。因此，如果阶乘是一个函数，那么它将被反复调用，但参数会减少 1。当参数为 1 或 0 时，它将返回 1。这可以是递归的基本情况。
示例
#include<iostream>
using namespace std;
long fact(long n){
if(n <= 1)
return 1;
return n * fact(n-1);
}
main(){
cout << "Factorial of 6: " << fact(6);
}输出
Factorial of 6: 720
更新于：2019年8月26日
3K+ 次浏览
广告