CSCI3160 L01 · Part 1/3 递归

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L01，第 1 部分 / 共 3 部分 · 原件 L01-Recursion-Repeating-Geometric-Series-未核.pdf（本地课件） p.1–9 定位：借汉诺塔说明递归假设、基本情形与递推展开，再演练选择分支的递归树。前后：下一份 Part 2

本讲按原件提纲分为：

p.1 标题页。p.2 依次列出 Recursion、Repeating、Geometric Series；以下按这个顺序阅读。p.3 分节页。

Recursion

递归假设不是循环论证（p.4）【新】

p.4 When dealing with a subproblem (same problem but with a smaller input), consider it solved, and use the subproblem’s output to continue the algorithm design.

递归（recursion）是在更小的同型问题上调用同一求解方法。设计时先相信“小规模已有答案”，专心解决怎样把那个答案变成当前答案；证明时再用归纳法兑现这个假设。两件事不能少：规模严格下降，以及到某个基本情形能直接停止。否则“假设子问题已经解好”可能只是把原题原样扔给自己。

汉诺塔的合法移动（p.5–7）【新】

题面（L01-Recursion-Repeating-Geometric-Series-未核.pdf · Tower of Hanoi · p.5–6）

p.5 There are 3 rods A, B, and C.

On rod A, n disks of different sizes are stacked in such a way that no disk of a larger size is above a disk of a smaller size.

The other two rods are empty.

p.6 Permitted operation: Move the top-most disk of a rod to another rod.

Constraint: No disk of a larger size can be above a disk of a smaller size.

Goal: Design an algorithm to move all the disks to rod B.

p.5 给起点，p.6 给合法操作与终点。关键障碍是最大盘被上面的 $n-1$ 个盘压住，必须先让它露出来。

图（p.7）：两次搬小盘夹着一次搬最大盘。元素：上图最大盘 $n$ 留在 A，其余 $n-1$ 个盘到 C；下图所有盘叠在 B，红色小盘堆表示第二次递归搬移。看什么：辅助柱的角色会改变，递归不能固定把 B 当作每次调用的目标。

p.7 的步骤是：把 $n-1$ 个小盘从 A 搬到 C；把最大盘从 A 搬到 B；把小盘从 C 搬到 B。每次小盘落在大盘之上，都合法。可把过程写成：

Hanoi(n, source, target, spare):
  若 n = 1：移动 source 的顶盘到 target；停止
  Hanoi(n-1, source, spare, target)
  移动 source 的顶盘到 target
  Hanoi(n-1, spare, target, source)

补充／算一遍（数字是我为演示取的，讲义没给）： $n=2$ 时，先小盘 A→C，再大盘 A→B，再小盘 C→B，共三步。每步移动的都是顶盘，终点也是 B，因而不是只算出了数量却没验证可行性。

补充：把递归调用当作一份合同。 Hanoi(m,s,t,u) 的前提是：需要搬的 $m$ 个盘合法地叠在 s 上，t、u 上若有盘，都比这 $m$ 个盘大；承诺是把这一小堆合法搬到 t。第一层的小盘操作可以把最大盘当作柱底的一部分，而不是要求三柱在每个子调用开始时全空。这样递归假设才真正适用于第二次调用。

以三个盘为例（规模是演示补充），用 1、2、3 表示从小到大：

步	移动	这一步在父调用中的角色
1	1：A→B	把上面两盘先搬到 C
2	2：A→C	同一子调用
3	1：B→C	第一个子调用完成
4	3：A→B	父调用只亲自搬最大盘
5	1：C→A	把 C 的两盘搬到 B
6	2：C→B	同一子调用
7	1：A→B	第二个子调用完成

递归栈记录“子调用返回后下一步做什么”，因此第一个子调用结束不会使整个算法结束。沿一条未返回的调用链只会有 $n$ 层；移动总次数指数多，不代表必须同时保存指数多层栈。

自测：把基本情形写为 n=1，能直接接受 n=0 的输入吗？

不能按现有伪代码直接接受；它会继续调用负数规模。可以明确合同仅允许正整数，也可以在实现中加入 n=0 直接返回。正确性证明需要与实际接受的输入范围一致。

递推式与递归练习（p.8–9）

p.8 Solving this recurrence gives $f(n)\le 2^n-1$ .

公式按讲义重排。p.8 的 $f(n)$ 是移动次数：两次规模 $n-1$ 的搬移，加一次最大盘移动，所以 $f(n)\le 2f(n-1)+1$ ，基本情形 $f(1)=1$ 。算一遍：沿用上节演示， $f(2)=2\cdot1+1=3$ ， $f(3)=2\cdot3+1=7$ 。这是指数增长，不因程序文本很短而变成快算法。把递推在主线展开：

\begin{aligned} f(n)&\le 2f(n-1)+1,\\ &\le 4f(n-2)+2+1,\\ &\le 2^j f(n-j)+(1+2+\cdots+2^{j-1}),\\ &=2^j f(n-j)+(2^j-1). \end{aligned}

第一行把两次小调用分别计入；再展开一次时，每个小调用又产生两个更小调用，所以系数变成 4，同时新增两次最大盘移动。做到 $j=n-1$ 后，小问题都是一个盘，代入 $f(1)=1$ ，上界变成 $2^{n-1}+2^{n-1}-1=2^n-1$ 。这里证明了课堂构造的上界；不能仅凭这个不等式断言所有算法的下界。保留原来的核验推导见附录 A1。

题面（同原件 · 递归练习 · p.9）

p.9 Use recursion to “redesign” the following algorithms: Binary search Quick sort

p.9 的二分查找：比较中点后只递归可能含目标的一半，空区间返回不存在；调用规模至少减半。快速排序：取枢轴，把更小与更大的元素分开，分别递归排序后与枢轴拼起来；空集或单元素停止。二分只追一侧，快排需要解决两侧，这个区别必须体现在递推式中。补充／算一遍（数字是我为演示取的，讲义没给）：快排 [3,1,2] 取 3，递归 [1,2]；再取 1，左空、右 [2]，合并为 [1,2]，最终 [1,2,3]。这说明递归调用返回的是完整排序结果，不是只把枢轴放到位。

由 p.9 要求展开的递归设计（符号化伪代码）：

BinarySearch(A, left, right, v):
  若 left > right：返回不存在
  mid = floor((left+right)/2)
  若 A[mid] = v：返回 mid
  若 v < A[mid]：返回 BinarySearch(A,left,mid-1,v)
  否则：返回 BinarySearch(A,mid+1,right,v)

QuickSort(S):
  若 size(S) <= 1：返回 S
  选一个枢轴 v
  L = S 中小于 v 的元素；R = S 中大于 v 的元素
  返回 QuickSort(L)，随后 v，随后 QuickSort(R) 的拼接

这里二分要求数组已升序，快排示例沿集合元素互异的约定；允许重复值时，应另设等于 v 的组。二分丢半边的理由是有序性，而快排必须将两侧都排序，因为输出要包含全部元素。二分的递推为 $T(n)\le T(\lceil n/2\rceil)+O(1)$ ；快排若左侧 a 个元素，递推为 $T(n)\le T(a)+T(n-a-1)+O(n)$ 。当枢轴总在极端，a 为 0 或 n−1，扫描成本相加会成为平方量级；p.9 的“用递归重写”本身没有保证枢轴总平衡。

对应往年题见附录 A4。

本讲核心考点

递归要有规模下降和基本情形；汉诺塔两次小调用夹一次移动（p.4–9；C 级）。
递归树的选与不选分支能枚举子集，最坏仍可能指数增长（A 级：Review-Quiz-2020T2 Q10）。

附录

A1 汉诺塔递推逐步展开（p.8）

从讲义给定的不等式出发，每展开一次都替换右侧的那个更小规模项：

\begin{aligned} f(n)&\le 2f(n-1)+1\\ &\le 4f(n-2)+2+1\\ &\le 2^jf(n-j)+(2^j-1)\\ &\le 2^{n-1}f(1)+(2^{n-1}-1)\\ &=2^n-1. \end{aligned}

第三行的常数和是 $1+2+\cdots+2^{j-1}=2^j-1$ ；令 $j=n-1$ 才到已知的基本情形。该推导证明的是这个构造的上界，没有额外证明所有可能算法的下界。

回到正文：递推式与递归练习（p.8–9）

A4 作业/往年题演练（非讲义内容）：递归树枚举子集和

题面（Review-Quiz-2020T2-题目.pdf · Q10 · p.2）

p.2 “10. Find all different subsets of sum 100 in {3, 7, 87, 24, 66, 27, 39, 73, 13} based on a recursion tree.”

按87、73、66、39、27、24、13、7、3的顺序建立“选/不选”递归树；排序只改变遍历顺序，不改变子集。状态是当前位置和剩余目标，选择该数就减去它，不选则目标不变；目标0报告，目标负或后面所有正数之和不足则剪枝。

选择87时剩13，唯一完成为{87,13}；87与更大的后继73、66、39、27、24均会超额。排除87而选73时剩27，可由{27}或{24,3}构成，得到{73,27}、{73,24,3}；其余小数13+7+3=23不足27。排除87、73而选66时剩34；可以由27+7或24+7+3构成，得到{66,27,7}、{66,24,7,3}，其余分支要么超额要么剩数不足。再排除66而选39时剩61；27+24+7+3=61成立，得到{39,27,24,7,3}；若不选27，剩数最多24+13+7+3=47不足61；若选27而不选24，剩13+7+3=23不足34；选27、24后需10，恰7+3。最后连39也不选时，总和27+24+13+7+3=74不足100，全部剪掉。

共六个子集，各自求和都是100。这个小输入能完整列出，不等于递归树算法一般为多项式时间；最坏情况下二选一仍有指数多分支。

回到正文：本讲结尾

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：L01-Recursion-Repeating-Geometric-Series-未核.pdf（本地课件），本部分 p.1–9；页码均为 PDF 页号。
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。