第二章 递归与策略的进化链
第二章 · 递归与策略的进化链
章节摘要：本章跟着"同一个问题、四种策略"的主线走——先教会计算机用递归把大问题拆小，再让动态规划记住拆出来的重复子问题，接着让回溯在解空间里学会回头与剪枝，最后用双指针证明有时候根本不用拆，换个观察角度就行。
一条主线
如果说第一章优化的是"数据放在哪"，本章优化的是"问题怎么想"。主线从一个所有算法书都绕不开的场景开始：面对规模为 n 的输入，直接算不动，怎么办？最自然的答案是递归——把问题拆成规模更小的同款问题。斐波那契、汉诺塔、归并排序，都是这个思路的直接受益者。但递归马上暴露出它的软肋：子问题在疯狂重复。于是动态规划登场，用一张表把算过的子问题记下来，指数级立即坍缩成多项式级。可还有一类问题，答案不是"最优值"而是"所有方案"，解空间像棵树一样铺开——这就是回溯的主场，它沿树深入、走不通就回退，而它的生死全看剪枝功夫。最后一站给出一个反直觉的结论：有些看似要嵌套扫描的问题，压根不用递归也不用表，两个指针相向而行或同向追赶，就能把平方级压成线性级。
四种策略不是并列的选项，而是层层递进的认知阶梯：递归是思维起点，动态规划是递归加上记忆化，回溯是递归加搜索树，双指针则是对"问题本身结构"的洞察红利。本章会反复把同道题用不同策略各解一遍，让你看清策略之间到底差在哪。
沿途站点
第一站递归与分治：建立"基准情形加自我调用"的思维模型，用斐波那契展示朴素递归的指数级重复，用归并排序展示分治"拆、解、合"的完整节奏，并给出递归深度与栈溢出的实战注意事项。第二站动态规划：从爬楼梯这道入门题出发，看清"重叠子问题加最优子结构"两个成立条件，沿着"自顶向下记忆化"与"自底向上递推"两条路线各走一遍，再用零钱兑换示范状态定义、转移方程、初始化这套完整设计流程，最后谈空间压缩——滚动数组如何把维度砍掉。第三站回溯：以全排列与子集为模板，画出解空间树的形状，讲清"选择、递归、撤销选择"三步循环，重点演示剪枝如何把不可能的分支提前掐断——同一个问题，剪枝好坏可能差出几个数量级。第四站双指针与滑动窗口：相向指针解决两数之和有序版与盛水容器，快慢指针解决移除元素与环检测，滑动窗口则把"定长窗口"进化成"可伸缩窗口"攻克无重复字符最长子串，并总结窗口伸缩的通用判定条件。
拐点与结论
本章最大的拐点在动态规划一节：当你说出"这道题用 DP"之前，真正的工作量在于找到那个能被记住的"状态"。很多同学背熟了转移方程却依然不会做题，原因是从未亲手体会过"朴素递归跑不动、画出递归树、发现重复节点、决定记忆化"这条进化路径本身。第个拐点在回溯与剪枝：解空间大小是纸面数字，实际耗时由你剪掉多少决定，所以回溯的优化不发生在代码层面，而发生在"尽早判定死路"的判断条件里。最后一个拐点属于双指针：它提醒我们，在急着上高级结构之前，先看看问题是否自带单调性——有序数组两端之和的增减规律，就是白送的速度。
读完本章你会获得一套策略选择直觉：要"所有方案"选回溯；要"最优值"且子问题重叠选动态规划；问题能拆成独立子问题选分治；数据自带顺序或单调性先试双指针。这套直觉在面试的高压下比任何模板都可靠。
读完你应该
- 手写斐波那契的朴素递归版、记忆化版与迭代版，并标出各自的复杂度与空间开销；
- 对爬楼梯、零钱兑换独立完成状态定义、转移方程推导与边界初始化，能用滚动数组压缩空间；
- 用回溯模板写出全排列、子集、组合总和，并至少说出两种剪枝策略及其生效条件；
- 用相向双指针解有序两数之和、用滑动窗口解无重复字符最长子串，说清窗口何时扩张何时收缩；
- 拿到新题时能按"最优值还是全部方案、子问题是否重叠、数据是否单调"三个问题快速选定策略。
下一章的接力
本章的策略大多跑在线性数据上；可当数据长成树形、或者问题需要"反复取最值""动态分组""前缀匹配"这类特殊操作时，通用策略就不够用了。第三章的主角是树与专门结构：二叉树遍历是递归思想在树上的正式亮相，堆把"反复取最值"从线性降为对数，前缀树把逐字符比较压缩成单步查表，并查集则用近乎常数时间的合并与查询统治动态连通性问题。它们每一个，都是针对个具体瓶颈进化出来的特效药。