前两周我们打造了一整套「度量」的尺子:数步数、看尾巴、O/Ω/Θ 定档。从这一课起,课程调转方向——开始造算法。第一件兵器叫递归 (recursion):把问题交给一个「会解同款问题」的黑盒,而那个黑盒就是你自己。听起来像作弊?只要每一步严格变小、有一个兜底的 base case,这不但合法,还自动附赠一份归纳法正确性证明。
教授开场就把底牌亮了:"arguably, this is the most important principle in algorithm design."(可以说是算法设计中最重要的原则。)它不是什么高深技巧,而是一种懒人哲学——归约。
先回望一下坐标。第 1–2 周,我们回答的都是「拿到一个算法,怎么评价它」:对不对(L1-1)→ 数多快(L1-2)→ O/Ω/Θ 定档(L1-3 至 2-4)。尺子已配齐,现在换问题:算法从哪来?本周开始回答「怎么设计」。
为什么说是懒人哲学?教授的自嘲:"We're computer scientists. We're lazy people."(我们是计算机科学家,我们是懒人。)现成能用的东西绝不重造——don't reinvent the wheels。面对新问题 A,第一反应永远是:手边有没有现成的零件能搭?
归约要求「B 是已经会解的问题」。递归的狂想是:让 B 就是 A 自己——拿一个还没写完的算法当黑盒,凭什么合法?
合法性的全部支点就是「更小」两个字。假设你已经能解 size 更小的同款问题,把它当黑盒,大问题就能搭在它上面。听起来像空中楼阁——但只要有一块真正落地的地基,楼就是稳的。这块地基,叫 base case。讲义:每个递归解法都由两部分组成:
第一个作品不整新活,请出全课程的老朋友——LinearSearch(L1-1 登场,L1-2 给它数出 T(n) = 10n + 7)。任务不变:找 k 在 A 中「最后一次出现」的位置。迭代版是从尾往头的一个循环;现在,换递归的眼光重写它。
教授课上现场发问:"In what case would the solution be trivial?"(什么情况下答案是显然的?)答:空数组。n = 0 时不用做任何检查——空数组里目标不可能存在,直接 return −1。教授自己都承认它 "felt trivial and felt useless"(显得又平凡又没用)——但请记住:base case 的职责本来就不是干活,是兜底。活全是递归干的,它只负责让一切能停下来。
变小不是白来的——教授:"you have to do some work to make it smaller."(得干点活才能换来变小。)干的活是:检查最后一个元素 A[n]。两种结局:命中 → 整个算法当场完工,return n——而且它必然是「最后一次出现」,因为它就是最后一个元素;未命中 → 你赚到了一条确定的信息:A[n] 不可能是答案。于是问题从 A[1..n] 缩成 A[1..n−1]——严格变小,可以安全递归了。
教授马上要没收这个玩具(他叮嘱:别追调用栈)。但没亲眼见过机器怎么转,「选择不看」就无从谈起。先痛痛快快违一次禁——逐帧看三种命运。
场景 A 的彩蛋:A[2] 也是 7,却从头到尾没被看过一眼——从尾部剥洋葱,天然保证「最后一次出现」。场景 C 则是 L1-2 说的 best case:目标恰好在扫描起点,递归深度 1。
讲义那行红字铁律,值得一个专门的破坏性实验:把三行代码里的安全装置逐个拆掉,看递归怎么死。
"I know mathematical induction sounds scary for some reason for many of you."(我知道归纳法不知为何让很多人发怵。)教授的脱敏疗法:让你看清——递归算法和归纳证明是同一枚硬币的两面 (two sides of the same coin),几乎逐行对应。
归纳法凭什么能证「任意大小都对」?两个零件的合力:base case 说「size 0 对」;归纳步说「比 n 小的全对 ⇒ n 也对」。组合起来:0 对 → 1 对 → 2 对 → 3 对 → ……多米诺一路推到任意大的输入。教授反复叮嘱对归纳假设的正确心态:"It's called a hypothesis... but I want you to think of it as a fact you know."(名字叫假设,但请把它当成已知事实来用。)
玩具正式没收。从今天起,面对递归算法的标准姿势只有两步——这是本课最重要的一页幻灯片。
找到「最小合法输入」,直接给出答案。它是 stop point——宁可显得没用,不可缺席。
做一点工作(检查一个元素、砍掉一半……),换来一个或多个更小的同款问题。逐条检查:每条递归路径都在向 base case 靠近吗?
把子问题的答案(神谕说了算)组合成当前答案。LinearSearch 的拼装最朴素:原样转交;后面几课的拼装会越来越有戏。
证明算法对最小输入正确。
假设算法对一切 size < n 的输入都正确。
证明 size n 时正确:算法归约出的子问题 size 全都 < n(被假设覆盖),且拼装步骤无误。收尾永远是那句:correctness follows from the inductive hypothesis。
三问的第二问该登场了:RecursiveLinearSearch 有多快?一动笔就发现不对劲——T(n) 的式子里,居然有 T 自己。
按 L1-2 的老规矩数 worst case(目标不存在):每一层调用「自己干的活」只有常数几步——判断 n == 0、比较 A[n] 与 k——记作 c;剩下的账,全记在「size n−1 的同款问题」头上。于是:
这种自我引用的式子叫递推式 (recurrence)——递归算法的标配。正式解法是本周四的主题;今天先用「剥洋葱」找找手感:
递归的坑,条条都是「终止」和「信任」出的事故。对号入座。
省掉的不是一行代码,是 stop point。§05 亲眼看过:一路冲穿调用栈。base case 宁可「看似无用」,不可缺席——它是安全网,不是装饰。
讲义红字铁律:每一步必须向 base case 靠近。原样调用自己 = 没有任何进展 = 无限循环。变小的方式可以是 n−1、n/2、剥掉一个结构……但必须严格。
归纳步写得再漂亮,不验证 base case 就一文不值:整条推理链悬在空中。反过来,只有 base case 没有归纳步也推不远。两条腿缺一不可。
教授:更复杂,而且 "doesn't give you much insight"。标准姿势永远两步:验 base case,信归纳假设——只亲手检查「变小 + 拼装」那一步。
四道,难度递增。C1 直接用上教授答疑里的观点;C4 把第一周的老朋友请回来对质。先动笔再看解。
提示:回想教授答疑——base case 是「算法需要处理的最小合法输入」。空数组有最大值吗?
提示:归纳的命题 P(n) 本身要带上「最大下标」三个字。命题太弱,归纳步会接不上。
提示:n = 8 时两个子问题的 size 各是多少?它们是 n−1 吗?
提示:这是谁?L1-1 的开场嘉宾。教授小学时想用一个下午解决它,没成。
无限次尝试,零压力。七道题,把「归约—递归—归纳」这条链各敲一遍。