中文（繁體）
中文（简体）
English
DSE ICT｜递归与算法效率 备课指引（导师用）｜二分搜寻为何只需 20 步
学生识写 for 循环，但一见“用递归写”就卡住，或者写出一个没有停机条件的函数。这一堂先把呼叫堆叠画出来，再比较线性与二分搜寻的步骤数，令“效率”变成数得出来的数字。
本堂目标 学生能够：① 追踪 factorial(4) 的呼叫堆叠，讲出 4 层、答案 24；② 写出有 base case 的递归函数并指出无 base case 会出现 RecursionError；③ 讲出在 1,048,576 笔已排序资料上用二分搜寻最多 20 次比较，而线性搜寻最多 1,048,576 次，相差约 52,429 倍；④ 判断两层循环是 O(n²)、每次把 n 减半是 O(log n)。
01 先备知识（开课前 3 分钟快检）
以下任何一项未过关，本堂就会卡住，先补该项：
| 技能 | 快检题 | 过关标准 |
|---|---|---|
| 函数与参数 | 呼叫函数时，参数放在哪里？ | 放进该次呼叫自己的 stack frame |
| for 循环 | 怎样把 1 到 n 加起来？ | 累加器由 0 开始，逐个加 |
| 排序 | 二分搜寻之前，资料必须怎样？ | 必须已排序 |
02 课堂流程（60 分钟）
| 时间 | 环节 | 导师做什么 | 学生做什么 |
|---|---|---|---|
| 0–8 分 | 一条问题开场 | 问：电话簿有一百万个名，找一个名要揭几页？ | 学生多数答“逐页揭” |
| 8–20 分 | 追踪 factorial | 并排写 factorial(4) → 4×factorial(3) → … → 1 | 画出 4 层 stack frame，答案 24 |
| 20–32 分 | base case 与深度 | 删掉 if n == 1 那一行，问会发生什么 | 讲出 RecursionError、深度等于 n |
| 32–44 分 | 二分搜寻步骤数 | 2^20 = 1,048,576，每切一半就少一个 2 | 得出最多 20 次比较 |
| 44–54 分 | 四类题型 | 追踪、补 base case、判断复杂度、算比较次数 | 每类做一题 |
| 54–60 分 | 离场检查 | 三题口头或书面 | 两题以下要重做 |
03 讲解脚本（照着说就可以）
第一幕：递归不是魔法，是一层层未做完的呼叫
写 factorial(n)：if n == 1: return 1；else: return n * factorial(n-1)。factorial(4) 未计完就要等 factorial(3)，factorial(3) 又等 factorial(2)，一直落到 factorial(1) 回传 1，才一层层乘上去：1 → 2 → 6 → 24。画四个并排的框，箭头向下是“等待”，向上是“回传”，学生就会明白“递归 = 用堆叠记住未做完的事”。
黑板画四个 stack frame，箭头向下是等待、向上是回传
第二幕：效率是步骤数，不是程式长短
把两张纸并排：线性搜寻由第一笔扫到最后一笔，最坏 1,048,576 次；二分搜寻每次砍一半，1,048,576 = 2^20，所以最多 20 次。52,429 倍的差距不是“少少快”，是由“等一小时”变成“等一秒”。再补一句：资料未排序就不能二分，排序本身要成本。
两张纸并排：线性 1,048,576 次 对 二分 20 次
第三幕：同一题目，两种写法都要交得出
叫学生用 for 循环写 sum(n)，再用递归写一次，然后比较：循环版用一个累加器，内存固定；递归版每一层占一个 stack frame，n = 1,000 已经接近 Python 预设的 recursion limit。结论要讲清：递归是表达方式，不会自动变快；很多时候循环更省资源。
板书 for 版与递归版并排，标 stack frame 数目
04 必教题型与步骤
| 题型 | 例子 | 步骤 | 答案 |
|---|---|---|---|
| 追踪 | 写出 factorial(4) 的呼叫顺序与答案 | 由最底层 factorial(1) 开始往回乘 | 4 层、答案 24 |
| 补完 | 给一个缺 base case 的函数，补上停止条件 | 先问“最细的 case 答案系几” | if n == 0: return 1 |
| 判断复杂度 | 两层 for 循环各跑 n 次 | 数最内层执行次数 | O(n²) |
| 计算 | 已排序 1,048,576 笔，二分搜寻最坏比较次数 | 找 2 的次方，或反复除 2 | 20 次 |
合理性检查（一定要教）：检查：log2(1,048,576) = 20，因为 2^20 = 1,048,576，答 21 或 19 都表示除错时多数或少数了一次。factorial(4) 的 stack 深度是 4，不是 24——24 是答案，不是层数。naive fib(6) 的呼叫次数是 25 次（2×fib(7)−1 = 2×13−1），而 fib(6) 的答案只是 8，这个落差正是“递归写得靓但效率差”的最佳证据。
05 独立练习三题
| 题目 | 答案 | 想观察什么 |
|---|---|---|
| naive fib(6) 总共几次函数呼叫？ | 25 次 | 2×fib(7)−1，fib(7)=13 |
| 1,000,000 笔资料，线性与二分搜寻最坏各几次？ | 1,000,000 次与 20 次 | 2^20 刚好超过一百万 |
| 这段程式错在哪：def total(n): return n + total(n-1) | 缺 base case | 会 RecursionError，n 永远不减到停 |
06 学生常见错误与纠正句
| 错误 | 学生通常这样写 | 导师这样说 |
|---|---|---|
| 漏写 base case | “个程式跑到爆，电脑坏了” | “先写停机那一行，再写行落去那一行；没有停机条件的递归等于死循环。” |
| 以为递归一定较快 | “递归高级些，所以快些” | “递归只系写法；fib(6) 递归要做 25 次呼叫，答案只系 8。” |
| 在未排序资料上做二分搜寻 | “我照样切一半，切到啱为止” | “未排序就切，等于乱猜；要么先 sort，要么用线性搜寻。” |
| 把 O(log n) 讲成“快一倍” | “log n 即系快一半” | “n 由 1,024 加到 1,048,576，即 ×1024，步数只由 10 加到 20，加 10 步。” |
07 家课建议（直接指到练习卷题号）
08 离场检查（最后 5 分钟）
| 题目 | 答案 | 判定 |
|---|---|---|
| factorial(5) 等于几，堆叠有几层？ | 120，5 层 | 错：重做第一幕 |
| 已排序 2^20 笔，二分搜寻最多几次比较？ | 20 次 | 错一题：下堂前重做代入 |
| naive fib(6) 几次呼叫？ | 25 次 | 错两题以上：回到第二幕 |
09 导师常问
递归一定要教吗？
DSE 课程要求学生读懂及修正递归程式，追踪与补 base case 是最常见考法。
要背时间复杂度符号吗？
不用背定义，但要能在 30 秒内把“两层循环”对应到 O(n²)、“每次减半”对应到 O(log n)。
为什么二分搜寻答 20 次而不是 10 次？
因为 2^20 才是 1,048,576，10 次只覆盖 1,024 笔。
本页为 TutorZone 导师备课指引，内容由 TutorZone 团队编写；题目与流程为原创，并非任何学校或出版社的教材。