目标

• 判断递归边界、递归调用次数与调用栈空间；
• 解释朴素递归中的重复子问题，并选择记忆化优化；
• 掌握分治法的分解、求解、合并过程；
• 区分分治与动态规划的子问题关系。

前置知识

建议先阅读递归基础与调用语义和分治模式与典型路径。

环境、输入与预期输出

• 环境：任意浏览器；建议准备纸笔绘制递归调用树。
• 输入：本页按顺序给出的 10 道选择题。
• 预期输出：独立作答记录，以及每道错题对应的递归边界或分治依据。

作答方法

1. 先明确函数语义、基准情况和子问题规模，再选择答案；
2. 涉及调用次数时画出完整调用树，不要只数递归边；
3. 点击“提交答案”后核对解析，并记录错误前提；
4. 完成全部题目后再查看答案总览。

题型覆盖与边界

类型	本 Lab 的处理方式
基础概念	递归边界、调用栈、局部变量和适用结构
递归优化	识别 Fibonacci 重复子问题与记忆化
分治模型	分解、求解、合并以及主定理基础
易错边界	明确阶乘基准条件后再统计调用次数

选择题

答题进度已答 0/10正确 0

第 1 题

难度★考点递归、终止条件、调用栈标识ch12-01-q01

下列关于递归算法的说法，错误的是（ ）。

查看提示

区分“函数调用开销”与“渐进时间复杂度”。

请选择一个答案

A递归算法必须存在能够到达的终止条件

B递归算法的时间复杂度一定高于对应的迭代算法

C递归算法的执行过程通常可以借助调用栈理解

D不同调用层次的局部变量分别保存在各自的栈帧中

第 2 题

难度★★考点递归、调用次数、基准情况标识ch12-01-q02

函数 factorial(n) 在 n == 1 时直接返回 1，否则返回 n * factorial(n - 1)。计算 factorial(5) 时，包含最初调用在内，函数总共被调用多少次？

查看提示

把首次调用和触发基准情况的最后一次调用都列出来。

请选择一个答案

A4

B5

C6

D10

第 3 题

难度★★考点Fibonacci、递归树、时间复杂度标识ch12-01-q03

未经记忆化的递归算法按 F(n)=F(n-1)+F(n-2) 计算 Fibonacci 数，其常用渐进时间上界是（ ）。

查看提示

观察同一个 F(k) 会在递归树中被重复计算多少次。

请选择一个答案

A$O(n)$

B$O(n^2)$

C$O(2^n)$

D$O(n\log n)$

第 4 题

难度★考点记忆化、重复子问题、Fibonacci标识ch12-01-q04

将朴素递归计算 Fibonacci 数的时间复杂度优化为 $O(n)$，最常用的方法是（ ）。

查看提示

优化的关键是让相同参数对应的子问题只计算一次。

请选择一个答案

A允许更深的递归

B用备忘录保存已经计算的子问题结果

C把递归改成广度优先搜索

D增加一个与原条件等价的递归边界

第 5 题

难度★★考点汉诺塔、递推式、递归标识ch12-01-q05

汉诺塔问题中，将 $n$ 个圆盘从 A 柱借助 B 柱移动到 C 柱，最少需要移动多少次？

查看提示

最大圆盘只移动一次，但它前后都要完整移动一次上方的圆盘。

请选择一个答案

A$2n$

B$n^2$

C$2^n-1$

D$2^n$

第 6 题

难度★考点递归、二叉树、适用场景标识ch12-01-q06

下列问题中，结构本身具有明显递归定义，因而最自然地适合用递归实现的是（ ）。

查看提示

寻找“子结构与整体属于同一类对象”的选项。

请选择一个答案

A数组顺序查找

B求两个整数的较大值

C二叉树的先序遍历

D使用循环累加数组元素

第 7 题

难度★考点分治、分解、合并标识ch12-01-q07

分治法的三个基本步骤是（ ）。

查看提示

对应英文 Divide、Conquer、Combine。

请选择一个答案

A分解、求解、合并

B排序、查找、输出

C递归、循环、判断

D输入、处理、输出

第 8 题

难度★★考点分治、子问题、适用条件标识ch12-01-q08

经典分治算法通常希望分解出的子问题具有什么性质？

查看提示

检查规模是否缩小、方法能否复用，以及子问题是否大量重叠。

请选择一个答案

A规模比原问题更大

B规模更小、形式与原问题相似，且子问题之间基本独立

C子问题数量必须恰好为 2

D子问题不能继续递归求解

第 9 题

难度★★考点分治、动态规划、重叠子问题标识ch12-01-q09

分治法与动态规划在子问题结构上的典型区别是（ ）。

查看提示

想一想为什么 Fibonacci 适合记忆化，而归并排序不需要缓存左右区间。

请选择一个答案

A分治只能递归实现，动态规划只能迭代实现

B分治子问题通常基本独立，动态规划子问题通常存在重叠

C分治的时间复杂度一定高于动态规划

D分治不需要组合子问题的解

第 10 题

难度★★考点主定理、递归式、时间复杂度标识ch12-01-q10

某分治算法满足 $T(n)=2T(n/2)+\mathrm{\Theta }(n)$，则其渐进紧确时间复杂度为（ ）。

查看提示

先计算 $n^{{\log }_{b}a}$，再与 $f(n)$ 比较。

请选择一个答案

A$\mathrm{\Theta }(n)$

B$\mathrm{\Theta }(n\log n)$

C$\mathrm{\Theta }(n^2)$

D$\mathrm{\Theta }(\log n)$

答案总览（建议完成全部题目后查看）

1. 第 1 题：B
2. 第 2 题：B
3. 第 3 题：C
4. 第 4 题：B
5. 第 5 题：C
6. 第 6 题：C
7. 第 7 题：A
8. 第 8 题：B
9. 第 9 题：B
10. 第 10 题：B

完成清单

• 10 道题均在展开答案前独立作答；
• 能写出汉诺塔移动次数的递推式；
• 能说明分治与动态规划对子问题关系的不同要求；
• 能根据递归式判断 $T(n)=2T(n/2)+\mathrm{\Theta }(n)$ 的复杂度。

思考题

1. 为什么递归写法更简洁，并不意味着时间复杂度一定更低？
2. 记忆化为什么改变 Fibonacci 的时间复杂度，却仍可能保留线性栈深度？
3. 子问题存在大量重叠时，为什么通常要考虑动态规划而非直接分治？

复盘

• 我是否在分析递归前先确认了基准情况？
• 我能否区分递归调用次数、递归深度和总工作量？
• 哪个错误选项利用了“一看到递归就认为更慢”的误区？