A Level · 主题 19

追踪递归与动态结构

比较搜索与排序、分析调用栈，并选择抽象数据类型。

课程区分 AS 主题 1–12 与 A Level 主题 13–20。示例包括剑桥伪代码与 Python。

向基本情况推进

递归解决方案定义停止情况，并让其他情况逐步接近它。调用栈保存等待较小调用返回的工作。解释递归结果时应同时追踪进入与返回过程。

二分搜索缩小已排序的候选范围，归并排序则分割数据再合并有序结果。应比较工作量与额外存储需求。算法的典型表现不能自动代表最坏情况。

栈遵循后进先出，队列遵循先进先出，二叉搜索树支持有序导航。数组与链接节点是实现方式。对有界实现应说明空与满的条件。

链式插入时，应先保留 next 引用再修改。树遍历中应明确当前节点相对孩子节点的访问顺序。用手工小例验证每个所需值恰好访问一次。

可交互

轮次 0比较次数 0交换次数 0

按“下一步”比较前两个数据项。

步骤 1 / 10

为什么正确递归算法仍可能在很深的输入上失败？查看答案

等待中的调用可能耗尽调用栈空间。正确性与资源限制是两个问题。

我们在编写本课程时参考了这些官方文件，用以确定考纲结构和课程要求。

Cambridge International · 9618 · 2027–2029 年考试