椰程信奥 · 教案
递归 · 教案
一、教学目标
| 维度 | 具体目标 |
|---|
| 知识与技能 | ① 说出递归三要素；② 独立写出放苹果、上台阶、十进制转二进制；
③ 掌握记忆化写法与递推改写。 |
| 过程与方法 | 通过可控动画把调用栈外显化；用重复节点统计数据驱动优化动机。 |
| 情感态度价值观 | 建立分治思想与工程判断（深度上千不递归）。 |
二、重点难点
| 类别 | 内容 | 突破方式 |
|---|
| 重点 | 递归三要素与栈帧 | 第 3–4 页动画 |
| 重点 | 放苹果分类递归 | 第 6 页递归树 + 第 7 页代码 |
| 难点 | 记忆化降复杂度不降深度 | 第 9 页追问"深度降了吗" |
| 难点 | "归"的顺序决定输出 | 第 10 页调换 cout 位置对比 |
三、教学过程
| 环节 | 教师活动 | 学生活动 | 设计意图 |
|---|
| ① 递与归 8′ | 第 3 页动画 | 报参数与返回值 | 栈可视化 |
| ② 栈帧 6′ | 第 4 页连点到溢出 | 说出溢出原因 | 深度直觉 |
| ③ 尾递归 4′ | 第 5 页对比 | 指出未完成的加法 | 理解"尾" |
| ④ 放苹果 9′ | 第 6–7 页 | 说明删 n>m 的后果 | 讲透失分点 |
| ⑤ 重复 6′ | 第 8 页统计 | 读重复比例 | 优化动机 |
| ⑥ 记忆化 6′ | 第 9 页填表 | 回答"深度降了吗" | 区分两维度 |
| ⑦ 进制 4′ | 第 10 页调换位置 | 预测输出 | 归的顺序 |
| ⑧ 检测 2′ | 第 14 页 | 完成 | 形成性评价 |
四、当堂检测标准
| 题号 | 正确答案 | 达标说明 |
|---|
| ① | 2 | 能说出盘子相同 → 顺序不同算同一种 |
| ② | 答案为 0 的子问题会被重算 | 能说出用 -1 初始化 |
| ③ | 看递归树是链还是分叉 + 深度 | 能说出深度上千改递推 |
五、板书设计
三要素：终止条件 / 递归调用（规模变小）/ 返回结果
放苹果：f(m,n)=f(m,n-1)+f(m-n,n) m==0||n==1 → 1 n>m → f(m,m) ★
记忆化：memo 用 -1 初始化；只降复杂度，不降栈深度
链 → 循环；分叉 → 递归+记忆化；深度上千 → 必须递推
六、易错预警清单
① 放苹果漏 n > m → m−n 变负 → 无限递归 RE；
② 终止条件漏 m == 0；
③ 记忆化用 0 作"没算过"标记 → 答案为 0 的子问题反复重算（用 -1）；
④ 以为记忆化能解决爆栈（不能）；
⑤ 台阶问题忘记每步取模；滑动窗口先加后减的顺序写反；窗口和用 int 溢出；
⑥ 十进制转二进制把 cout 写在递归调用之前 → 输出反序。