🌱 第一章：什么是递推？
——《会自己长大的数字树》
1、想象有一棵神奇的树 🌳
（1）第一天，树上只有 1片叶子
（2）第二天，每片叶子会长出 2片新叶子
（3）我们记录每天的叶子数量：
| 天数 | 叶子数 |
|---|---|
| 第1天 | 1 |
| 第2天 | 2 |
| 第3天 | 4 |
| 第4天 | 8 |
| 第5天 | 16 |
（4）你会发现一个秘密：
👉 今天的叶子数 = 昨天的叶子数 × 2
这就是：递推公式
2、🎯 递推的本质
（1）用前面的结果，推出后面的结果
就像：
今天 = 昨天 推出来的
未来 = 现在 推出来的
这就叫：
（2）✅ 递推（一步一步推出来）
（3）这是GESP四级C++考试大纲中，必考的算法。
🌟 第二章：用生活故事理解递推
1、🐰故事：兔子生宝宝
（1）农场有兔子：
第1个月：1只兔子
第2个月：1只兔子
（2）从第3个月开始：
每只成熟兔子每个月生1只新兔子
2、算一算：
| 月份 | 兔子数 |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
3、递推的秘密：
第n月兔子数 = 第n-1月兔子数 + 第n-2月兔子数
4、这就是著名的：
🌟 斐波那契数列
🧠 第三章：递推的3个关键部分
任何递推必须有：
1、 初始值（最开始）
比如：
第1天 = 1
第2天 = 1
否则无法开始
就像没有第一块积木，无法搭房子 🧱
2、递推公式（核心）
比如：
a[i] = a[i-1] + a[i-2]
意思：
第i个 = 前两个推出来
3、递推的顺序
必须：
先算小的
再算大的
不能跳着算
💻 第四章：最基础递推模板
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int a[100];
// ① 初始值
a[1] = 1;
a[2] = 1;
// ② 递推
for(int i = 3; i <= n; i++)
{
a[i] = a[i-1] + a[i-2];
}
// ③ 输出
cout << a[n];
return 0;
}
🌈 第五章：故事例题1《爬楼梯的小朋友》
1、小明要爬楼梯 🧒
（1）每次可以：
走1步
或
走2步
（2）问：
爬到第n级，有多少种方法？
2、我们画图：
（1）画一画
第1级： 1 1种
第2级：1+1 2 2种
第3级：1+1+1 1+2 2+1 3种
第4级：1+1+1+1 1+2+1 2+1+1 1+1+2 2 + 2 5种
（2）找规律：
f[n] = f[n-1] + f[n-2]
（3）因为：
最后一步：
可能从 n-1 来
可能从 n-2 来
3、参考程序
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int f[100];
f[1] = 1;
f[2] = 2;
for(int i = 3; i <= n; i++)
{
f[i] = f[i-1] + f[i-2];
}
cout << f[n];
return 0;
}
🌈 第六章：故事例题2《存金币的小猪》
1、小猪每天存金币 🐷
（1）第1天：存1个
以后每天比前一天多存2个
（2）问第n天存多少？
2、填表格：
1 1+2=3 3+2= 5 5+2=7 7+2=9
这是一个等差数列！
3、递推公式：
a[i] = a[i-1] + 2
4、核心程序：
a[1] = 1;
for(int i=2;i<=n;i++)
{
a[i] = a[i-1] + 2;
}
🌈 第七章：故事例题3《会繁殖的细菌》
1、细菌每天：
变成昨天的3倍
2、递推公式：
a[i] = a[i-1] * 3;
🌟 第八章：递推万能模板
int a[100];
a[1] = 初始值;
a[2] = 初始值;
for(int i = 2; i <= n; i++)
{
a[i] = 用 a[i-1] 或 a[i-2] 计算;
}
🌟 第九章：递推和普通循环的区别
1、普通循环：
只是重复
2、递推：
👉 用“以前的结果”
3、例如：
（1）普通循环：
for(int i=1;i<=n;i++)
{
cout<<i;
}
（2）递推算法：
a[i] = a[i-1] + 5;
使用递推公式，生成新的结果，用到了上一轮刚刚生成的结果。
第十章：GESP考试最常见递推类型
类型1：每次加
a[i]=a[i-1]+k;
类型2：每次乘
a[i]=a[i-1]*k;
类型3：前两个相加
楼梯问题、兔子问题
a[i]=a[i-1]+a[i-2];
⭐⭐⭐⭐⭐考试最爱
类型4：平方递推
a[i]=a[i-1]*a[i-1];
第十一章：小学生记忆口诀 🎵
递推递推不要猜
前面结果推出来
先有开始第一项
再用公式往后排
🌟 第十二章：图解理解
想象：
a[1] → a[2] → a[3] → a[4] → a[5]
↓ ↓ ↓ ↓
开始 推出 推出 推出
像多米诺骨牌一样倒下
🌟 第十三章：GESP考试标准递推模板
#include <iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int a[1000];
a[1]=...;
a[2]=...;
for(int i=3;i<=n;i++)
{
a[i]=...;
}
cout<<a[n];
return 0;
}
🌟 第十四章：一句话总结
递推就是：
👉 用过去，推未来
就像是
🌱种子 、小苗 、变大树
一步一步长出来
转载自CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/weixin_60445850/article/details/158539623
