GESP5级C++考试语法知识（十一、递归算法（一））

第一章什么是递归“套娃小精灵”的故事1、 想象一个魔法世界有一个小精灵它不会做复杂的事情但它有一个绝招遇到问题就把问题变成一个“更小的同样问题”然后再让自己去做这就是——递归2、 递归的本质 一个函数调用自己就像这样void f() { f(); // 自己调用自己 }⚠️ 但这样会无限循环所以必须有3、 递归三大要素1️⃣ 终止条件出口 不然就会无限调用爆炸2️⃣ 递归公式规律 大问题 小问题3️⃣ 缩小规模 每次问题都变小 第二章经典故事——爬楼梯1、 故事1小明要爬楼梯每次可以走1步或走2步2问爬到第 n 阶有多少种方法2、 思考过程1假设f(n) 表示到第 n 阶的方法数2 分情况到第 n 阶最后一步可能是从 n-1 走1步从 n-2 走2步3 所以f(n) f(n-1) f(n-2)3、 终止条件f(1) 1 f(2) 24、 C代码int f(int n) { if(n 1) return 1; if(n 2) return 2; return f(n-1) f(n-2); }5、 调用过程像树一样算 f(5)f(5) ├── f(4) │ ├── f(3) │ │ ├── f(2) │ │ └── f(1) │ └── f(2) └── f(3) ├── f(2) └── f(1)6、 会发现很多重复计算 第三章递归的时间复杂度1、 结论先记住对于上面的代码 时间复杂度是O(2^n)2、 为什么1因为 每次都会分成两条路像一棵“爆炸树”f(n) / \ f(n-1) f(n-2) / \ ...2 节点数量 ≈ 2^n3 小结一句话递归越分叉时间越慢 第四章递归的空间复杂度1、 空间来自哪里 来自函数调用栈2、 想象函数调用像叠盘子 f(5) ↓ f(4) ↓ f(3) ↓ f(2) ↓ f(1) 最深n 层3、 结论 空间复杂度O(n) 第五章递归的三大优化策略 优化1记忆化避免重复计算 思路 算过的结果存起来 C实现int dp[100]; int f(int n) { if(n 1) return 1; if(n 2) return 2; if(dp[n]) return dp[n]; return dp[n] f(n-1) f(n-2); } 效果 时间复杂度O(n) 从指数 → 线性 优化2改成循环递推 思路 既然是从小推大那就不用递归 代码int f(int n) { int a 1, b 2; for(int i 3; i n; i) { int c a b; a b; b c; } return b; } 优势不会爆栈更快更省空间 空间复杂度O(1) 优化3剪枝减少不必要计算 用在搜索问题DFS比如 找路径 走迷宫 思想 “这条路不可能成功就别走了” 示例void dfs(int step) { if(step 10) return; // 剪枝 // 继续搜索 } 第六章什么时候用递归 看到这些关键词可能想到递归树 二叉树、DFS分治归并排序回溯全排列搜索迷宫 最终总结 递归就像一个聪明的小精灵1️⃣ 不会做大问题 就把问题变小2️⃣ 一直变小 直到能解决3️⃣ 再把答案一点点拼回来 一句话记住递归“大问题 小问题 自己” 课后练习试试写1️⃣ 求 n 的阶乘2️⃣ 斐波那契数列3️⃣ 打印 1~n接下来我们继续学习递归的记忆化搜索 第一章为什么需要记忆化“健忘的小精灵”1、 故事还是那个递归小精灵 ‍♂️它很努力但有个大问题它每次都会忘记自己算过什么2、比如它在算f(5)结果它算了一次 f(3)又算了一次 f(3)又又算了一次 f(3)… 就像一个人写作业每题都重新推一遍3、 重复计算图f(5) ├── f(4) │ ├── f(3) │ │ ├── f(2) │ │ └── f(1) │ └── f(2) └── f(3) ├── f(2) └── f(1)f(3) 被算了很多次 第二章记忆化搜索的核心思想1、 一句话算过的结果存起来下次直接用2、 类比像这样‍ 小朋友做题第一次认真算 ✅第二次直接抄答案 第三章经典实例爬楼梯升级版1、 问题还是爬楼梯 每次走 1 或 2 步 求到第 n 阶的方法数2、❌ 普通递归慢int f(int n) { if(n 1) return 1; if(n 2) return 2; return f(n-1) f(n-2); }3、 时间复杂度O(2^n)爆炸 第四章加入记忆化核心1、 第一步准备一个“记忆本”int dp[100]; // 初始为0 dp[n] f(n)2、 第二步查询是否算过if(dp[n] ! 0) return dp[n];3、 第三步算完要存dp[n] f(n-1) f(n-2);4、 完整代码#include iostream using namespace std; int dp[100]; int f(int n) { if(n 1) return 1; if(n 2) return 2; if(dp[n] ! 0) return dp[n]; // 查表 dp[n] f(n-1) f(n-2); // 计算并存 return dp[n]; } int main() { cout f(10) endl; } 第五章复杂度变化超级重要1、 没有记忆化 每个状态重复计算 时间复杂度O(2^n)2、 有记忆化 每个 n 只算一次 时间复杂度O(n) 直接从“爆炸级”变“线性级”3、 空间复杂度dp数组O(n)递归栈O(n) 总空间O(n) 第六章再来一个更强例子背包问题雏形1、 问题有 n 个物品每个物品可以选或不选 问有多少种选法2、 递归思路f(i) f(i-1) f(i-1) 选 or 不选3、❌ 问题 同样会重复计算4、 记忆化版本 C代码int dp[100]; int f(int n) { if(n 0) return 1; if(dp[n]) return dp[n]; return dp[n] f(n-1) f(n-1); }5、 本质 把“树形递归”压缩成“线性计算” 第七章记忆化搜索模板必须掌握 通用模板int dp[100]; // 初始化为0 int dfs(int x) { // 1️⃣ 终止条件 if(边界) return 值; // 2️⃣ 查缓存 if(dp[x] ! 0) return dp[x]; // 3️⃣ 递归计算 dp[x] dfs(子问题); // 4️⃣ 返回结果 return dp[x]; } 第八章什么时候用记忆化看到这些情况就用1、 特征✅ 有“重复子问题”✅ 是递归✅ 可以用数组存状态2、 常见题型斐波那契数列爬楼梯背包问题树形DPDFS 状态 第九章递归 vs 记忆化 vs 动态规划方法本质速度递归暴力慢记忆化递归 存储快DP迭代更快 关系记忆化搜索 自顶向下的动态规划 最终总结 记忆化搜索就是算过就记住下次直接用 一句话理解“递归 小本本 高级算法”