目录
概念：递归是指函数直接或间接调用自身的过程
递归函数的一个条件，当满足该条件时，递归终止，避免无限递归。可以理解为直接解决极小规模问题的方法。
递归函数中的语句，用于解决规模更小的子问题，再将子问题的答案合并成为当前问题的答案。
递归函数的基本结构如下：
返回类型 函数名（参数列表）{
//基本情况（递归终止条件）
if(满足终止条件){
// 返回终止条件下的结果
}
//递归表达式（递归调用）
else{
//将问题分解为规模更小的子问题
//使用递归调用解决子问题
//返回子问题的结果
}
}实现过程：
1.将大问题分解为规模更小的子问题
2.使用递归调用解决每个子问题
3.通过递归终止条件来结束递归
设计时需要注意的细节：
1.确保递归一定能到递归出口，避免无限递归，这可能导致TLE（超时）、MLE（超内存）或RE(运行错误)。
2.考虑边界问题，有时候递归出口不止一个。
3.避免不必要的重复计算，尽可能优化递归函数的性能（例如使用记忆化）。
递归的特点：
1.直观、简洁、易于理解和实现
2、适用于问题的规模可以通过递归调用不断减小的情况
3、可以处理复杂的数据结构和算法，如树和图的遍历
4、存在栈溢出风险（栈空间一般只有8MB，所以递归层数不宜过深，一般不超过1e6层）
循环的特点：
1、直接控制流程，效率较高
2、适用于问题的规模没有明显的缩减，或者需要特定的迭代次数
3、适合处理大部分的动态规划问题
在部分情况下，递归和循环可以相互转换
已知F(1)=F(2)=1;
n>3时F(n)=F(n-1)+F(n-2)
输入n，求F(n)，n<100000,结果对le9+7取模
#include<iostream>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
const ll p = 1e9 + 7;
//带备忘录递归
ll dp[N];
ll fib(int n)
{
if (dp[n])return dp[n];//计算过的斐波那契那一位就不会重复计算了
if (n == 1 || n == 2)return 1;
else return dp[n] = (fib(n - 1) + fib(n - 2))%p;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n; cin >> n;
cout << fib(n) << endl;
system("pause");
return 0;
}我们要求找出具有以下质数的个数（包含输入的自然数n）
先输入一个自然数n（n<1000），然后对此自然数按照如下方法进行处理
1.不做任何操作
2、在它的左边加上一个自然数，但该自然数不能超过原数的一半
3、加上数后，继续按此规则进行处理，直到不能再加自然数为止
输入一个正整数n
输出一个整数，表示具有该质数的个数
输入6? ? ? ? 输出6
#include<iostream>
using namespace std;
const int N = 20;
int a[N];
int dfs(int deep)//deep表示当前的深度
{
int res = 1;
for (int i = 1; i <= a[deep - 1] / 2; ++i)//不能超过原来数字的一半
{
a[deep] = i;
res += dfs(deep + 1);//向下一层去搜索
}
return res;
}
int main()
{
int n; cin >> n;
a[1] = n;
cout << dfs(2) << endl;
system("pause");
return 0;
}首先，初始状态a[1]=n，拿n=6来说，dfs(2)进入后?
在for循环中for(i=1;i<=6/2=3;i++)即三个状态
1、a[2]=1 ???????????????? ?res+=dfs(3)
2、a[2]=2 a[3]=1????????res+=dfs(3)+dfs(4)
3、a[2]=3 a[3]=1? ? ? ? res+=dfs(3)+dfs(4)
所以最后结果为6