课程信息
B2.4.4–5 · HL · 已规划

递归及其应用

跟踪递归调用到达基本情况并逐层返回，再探索相同思路如何支持更复杂的应用。

55 分钟

本节课资源

课堂活动 ↓ 打开 Python 实验室 →
动画： 递归求和快速排序 · HL 应用二叉树遍历 · HL 应用分形树 · HL 应用
Python · 逐步执行

递归求和

观察调用如何逐层增加、到达基本情况，再按相反顺序返回。

选择“播放”或“下一行”，跟踪 Python 的执行过程。

Python 实现

高亮表示下一条将执行的语句。数值显示执行该行之前的状态。

def recursive_sum(n):    if n == 0:        return 0    subtotal = recursive_sum(n - 1)    return n + subtotal

B2.4.5：简单的非分支递归函数。每次调用最多产生一次递归调用。对于非负的 n，时间复杂度为 O(n)，调用栈辅助空间为 O(n)。循环实现可使用 O(1) 辅助空间。

学完本节课后

  • 识别基本情况，并解释如何逐步接近它。
  • 构建并跟踪简单的非分支递归函数。
  • 解释快速排序、树遍历与分形绘制中的递归。
  • 计入当前递归调用所使用的内存。

完成本节课

01 · 10 分钟

预测结果

使用递归求和动画。预测 recursive_sum(4)，再逐行跟踪 Python。解释为什么 recursive_sum(0) 会停止。

02 · 15 分钟

跟踪调用栈

记录每个当前调用的 n。在基本情况处暂停，再预测各调用完成时返回的值。

03 · 15 分钟

构建与测试

编写简单的非分支递归函数。测试其基本情况及一个较小输入。解释每次调用如何更接近终止。

04 · 10 分钟

探索应用

使用快速排序、树遍历与分形动画解释更小的子问题。这些分支递归示例用于说明应用；B2.4.5 不要求完整实现它们。

05 · 5 分钟

比较内存

比较递归求和与循环。解释等待返回的递归调用为什么需要额外内存。

下课前

离堂问题

要让函数终止，基本情况与每次递归调用必须满足什么条件？