函数与递归教案

算法入门期 Week1 周末教案：函数与递归

• 主题：从“代码复用”到“分而治之”

• 时间：周六 9:00–12:00（精讲 + 互动），14:00–17:00（实战 + 代码评审）

• 目标：

1. 理解函数的价值，掌握函数定义、调用、参数传递；

2. 建立递归思维，掌握递归三要素，能独立编写简单递归函数；

3. 通过“汉诺塔”等经典问题，体会“分而治之”的思想。

一、周六上午：函数与递归精讲（3小时）

1. 开场与回顾（9:00–9:30）

2. 函数基础：从“重复代码”到“函数封装”（9:30–10:30）

3. 递归思想：自己调用自己（10:40–12:00）

二、周六下午：实战演练 + 代码评审（3小时）

1. 综合项目：“汉诺塔”思想实践（14:00–15:30）

2. 代码评审与优化（15:40–17:00）

3. 本周作业布置（17:00–17:15）

三、周日专项特训：递归与函数综合应用（3小时）

1. 模拟测试（9:00–10:00）

评分标准：

• 代码正确性（60%）；

• 递归三要素是否清晰（20%）；

• 代码规范（注释、缩进，20%）。

2. 错题复盘与总结（10:10–12:00）

四、配套资源

1. 《函数与递归避坑手册》

• 函数定义时忘记写返回值类型（默认int，但不规范）；

• 递归函数缺少终止条件（导致栈溢出）；

• 值传递时试图修改实参（如void swap(int a, int b) { int t=a; a=b; b=t; }无效）。

• 常见错误：

• 记忆口诀：

  “函数三要素，类型名参表；递归两要点，终止和递推；调用自己时，别忘停一停。”

2. 《递归流程图模板》

• 提供空白流程图模板，学生可手绘递归调用过程（如factorial(3)的调用栈），强化理解。

3. 推荐视频

• B站“正月点灯笼”的《函数与递归》系列（生动形象，适合入门）。

一、课堂互动小游戏（配合周六上午“函数与递归精讲”）

游戏1：函数“传话游戏”（9:30–9:45，函数参数传递环节）

目的：让学生直观感受值传递 vs 地址传递的区别。

玩法：

1. 选 3 个学生 A、B、C，再选 1 个学生 D 当“记录员”。

2. 老师悄悄给 A 一个数字（比如 5），告诉 A：

• 你是“值传递”，只能把数字抄下来，不能拿老师的纸条；

• 然后按规则“+1”后，把新数字传给 B。

3. B 是“地址传递”，老师给 B 看原始纸条，B 按规则“+1”后，直接在纸条上改。

4. 最后让 A、B 分别报出自己手里的数字，D 记录。

5. 老师问全班：A 和 B 手里的数字分别是多少？为什么不一样？

代码对应：

• A 的行为对应值传递：void func1(int a) { a++; }

• B 的行为对应地址传递：void func2(int *a) { (*a)++; }

效果：

学生通过“抄数字”和“改纸条”的对比，很容易理解：

• 值传递只是改了“复印件”，原件不变；

• 地址传递是改了“原件本身”。

游戏2：递归“故事接龙”（10:40–10:55，递归思想引入环节）

目的：用故事理解“自己调用自己”的递归结构，并自然引出终止条件。

玩法：

1. 老师先说第一句：

   “从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事。”

2. 然后老师说：

   “故事的内容是——从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事……”

3. 邀请学生接龙，要求必须原样重复这句话，不能改词。

4. 连续接 3 轮后，老师突然打断：

   “等一下，这个故事能一直讲下去吗？如果不加个‘结束’，我们会怎样？”

5. 引导学生说出：会一直讲不完，就像死递归。

代码对应：

• 故事内容 = 递归函数体；

• 接龙 = 自己调用自己；

• 必须加一句“讲完了” = 终止条件。

效果：

学生笑一笑的同时，就记住了：

• 递归就是“套娃式”地重复自己；

• 没有终止条件就会无限循环，程序会“讲不完”，现实里就是栈溢出。

游戏3：汉诺塔“真人版挑战”（14:00–14:20，汉诺塔思想实践环节）

目的：用身体参与的方式，理解“分而治之”的递归步骤。

准备：

• 3 张桌子/椅子，分别当 A、B、C 三根柱子；

• 3–5 个大小不同的物品，如：

• 大纸箱 = 大盘子

• 小盒子 = 小盘子

• 橡皮 = 最小盘子

玩法：

1. 把 3 个物品按“大在下、小在上”放在 A 桌。

2. 老师宣布规则：

• 一次只能移动一个物品；

• 大盘子不能压在小盘子上；

• 目标是把所有物品从 A 移到 C。

3. 先让全班一起想：

• 2 个物品时，怎么移？

• 3 个物品时，能不能先动最下面的？

4. 请 1 名学生上来，按“先移上面 2 个，再移最下面 1 个，再把 2 个移过去”的思路试一遍。

5. 老师边看边说：

• “你现在做的，就是把 3 个盘子的问题，拆成了 2 个盘子的子问题。”

• “这就是递归的‘分而治之’！”

效果：

学生通过亲自“搬箱子”，能直观看到：

• 移动 n 个盘子 = 移动 n-1 个盘子 + 移动 1 个 + 再移动 n-1 个；

• 这就是汉诺塔递归的核心思想。

二、趣味例题（配合周六下午“实战演练 + 代码评审”）

趣味题1：递归求“猴子吃桃”（15:00–15:20，函数综合应用）

题目背景：

猴子第一天摘了若干个桃子，当天就吃掉一半再多 1 个；

第二天又吃掉剩下的一半再多 1 个；

以后每天都这样吃，到第 10 天早上只剩 1 个桃子。

问：第一天摘了多少个桃子？

代码实现（递归）：

cpp
cpp
下载
复制
#include<iostream>usingnamespace std;// day: 第几天早上（day=10 时剩1个，day=1 是第一天早上）intpeach(int day){if (day == 10) {          // 终止条件：第10天早上剩1个return1;    }// 递推关系：第day天的桃子 = (第day+1天的桃子 + 1) * 2return (peach(day + 1) + 1) * 2;}intmain(){    cout << "第一天摘了 " << peach(1) << " 个桃子" << endl;return0;}

互动设计：

• 先让学生用倒推法在纸上算：

• 第 10 天：1 个

• 第 9 天：(1+1)×2 = 4 个

• 第 8 天：(4+1)×2 = 10 个

• 再问：

• 如果改成“第 n 天剩 m 个，求第 1 天”，怎么用函数写？

• 让学生自己把 peach函数改写成带两个参数的通用版本，训练参数设计能力。

亮点：

• 比普通“阶乘、斐波那契”更有故事感，学生更愿意算；

• 能自然引出逆向递推的递归思路。

趣味题2：函数“角色扮演游戏”（RPG）伤害计算器（15:20–15:40，函数综合应用）

题目背景：

设计一个简单的“打怪”小系统：

• 角色有攻击力 atk和暴击率 critRate（0~100%）；

• 怪物有防御力 def；

• 每次攻击伤害 = 攻击力 - 防御力，如果暴击则伤害翻倍；

• 用函数实现：

1. 计算单次伤害 calcDamage(atk, def, critRate)；

2. 计算 n 次攻击总伤害 totalDamage(atk, def, critRate, n)。

代码实现：

cpp
cpp
下载
复制
#include<iostream>#include<cstdlib>#include<ctime>usingnamespace std;// 计算单次伤害intcalcDamage(int atk, int def, int critRate){int damage = atk - def;if (damage < 0) damage = 0;  // 伤害不能为负// 随机数模拟暴击（0~99 与 critRate 比较）if (rand() % 100 < critRate) {        damage *= 2;    }return damage;}// 计算n次攻击总伤害inttotalDamage(int atk, int def, int critRate, int n){int sum = 0;for (int i = 0; i < n; i++) {        sum += calcDamage(atk, def, critRate);    }return sum;}intmain(){srand(time(0));  // 随机种子int atk = 20, def = 5, critRate = 30, n = 3;    cout << n << " 次攻击总伤害：" << totalDamage(atk, def, critRate, n) << endl;return0;}

互动设计：

• 先让学生自己设计：

• 单次伤害函数需要哪些参数？

• 总伤害函数要不要用循环？

• 再问：

• 如果想加“吸血”功能（伤害的一部分回复为生命值），函数要怎么改？

• 让学生现场加一个新函数 addLifeSteal(...)，训练函数扩展能力。

亮点：

• 用“打怪”这种学生熟悉的场景包装函数与循环；

• 能顺带练习随机数、条件判断、循环、函数调用的综合使用。

趣味题3：递归“谢尔宾斯基三角形”（选做，16:00–16:20，拓展提升）

题目背景：

用“*”画一个谢尔宾斯基三角形：

• 第 1 级：1 个“*”；

• 第 2 级：3 个“*”，排成小三角形；

• 第 3 级：把每个小三角形再分成 3 个更小的三角形……

  用递归函数 draw(int level, int x, int y)实现，其中：

• level是当前层级；

• (x, y)是当前三角形的顶点位置。

代码实现（核心逻辑）：

cpp
cpp
下载
复制
#include<iostream>usingnamespace std;voiddraw(int level, int x, int y){if (level == 0) {  // 终止条件：层级为0，画一个点        cout << "*";return;    }// 画当前层级的三角形（简化为打印3个子问题）draw(level - 1, x, y);                    // 左上draw(level - 1, x + (1 << (level-1)), y); // 右上draw(level - 1, x + (1 << (level-2)), y + (1 << (level-1))); // 下方}intmain(){int level = 3;draw(level, 0, 0);return0;}

互动设计：

• 先在纸上画：

• 第 1 级、第 2 级、第 3 级分别长什么样；

• 再问：

• 第 4 级会多多少“小三角”？

• 让学生用“分形”的角度理解：

• 大三角形 = 3 个小三角形 + 某种排列；

• 这就是典型的递归分形结构。

亮点：

• 图形化输出，比纯数字更有趣；

• 能让学生看到递归在分形、图形学中的应用，打开视野。

三、使用建议

1. 时间控制

• 时间充裕时，讲完主例题后再讲一个；

• 时间紧时，可以只做游戏，把趣味题留作课后选做。

• 每个游戏控制在 10–15 分钟 内，避免影响主线进度；

• 趣味题可以作为“加餐”：

2. 与知识点强绑定

• 讲“值传递/地址传递”时，用传话游戏；

• 讲“递归思想”时，用故事接龙；

• 讲“分而治之”时，用汉诺塔真人版；

• 讲“函数综合应用”时，用猴子吃桃、RPG伤害计算。

3. 学生参与感

• 游戏尽量让学生上台/出声参与，老师负责引导和总结；

• 趣味题可以让学生先说思路，再写代码，老师只做点拨。

4. 难度分级

• 基础弱的学生：重点参与游戏 + 做“猴子吃桃”这种有明显数学规律的题；

• 基础好的学生：可以挑战“RPG伤害计算器”的扩展，或“谢尔宾斯基三角形”的递归绘图。