# 5算法

## 阅读入口

* [计算思维](/knowledge/cs/algorithms/computational-thinking/)
* [递归](/knowledge/cs/algorithms/recursion/)
* [分治法](/knowledge/cs/algorithms/divide-and-conquer/)
* [贪心算法](/knowledge/cs/algorithms/greedy-algorithm/)
* [动态规划](/knowledge/cs/algorithms/dynamic-programming/)
* [老鼠走迷宫与回溯](/knowledge/cs/algorithms/maze-backtracking/)

## 递归的结构

### 写递归前先回答三个问题

1. **基线是什么？** 最小规模取什么值，答案是什么？
2. **规模如何减小？** 每一步把问题缩小多少，是否一定到达基线？
3. **结果如何组合？** 子问题的返回值怎样合成当前问题的答案？

### 执行顺序

递归调用不会立刻返回结果：当前调用先暂停，等子调用结束后再继续执行它后面的语句。因此，打印语句写在递归调用之前还是之后，会得到完全不同的输出顺序。汉诺塔的移动顺序就是由三次调用的先后关系决定的。

每次调用都会占用一个栈帧；调用链的展开与回退见[函数调用与栈帧](/knowledge/cs/computer-architecture/function-call-stack/)。

### 线性递归与树形递归

* **线性递归**：每次只调用一次自身，调用链是一条线。递归加法属于这一类，规模每步减少1。
* **树形递归**：每次分解成多个子调用，调用过程形成一棵树。汉诺塔每次产生两个规模 $n-1$ 的调用，移动次数满足 $M(n)=2M(n-1)+1$，$M(1)=1$，解得 $M(n)=2^n-1$。

树形递归的调用次数可能随规模指数增长，写之前应先估计调用总量。

[来源：递归](/knowledge/cs/algorithms/recursion/#structure)

5.2用递归加法、汉诺塔和归并建立这套结构，5.7的`factors`也是同一种写法。读后面几节时，凡是新的递归函数，都先回到“基线、规模、组合”这三个问题上。

## 分治的适用条件

分治能成立，通常需要同时满足以下条件：

* **子问题与原问题同型**：可以用同一个函数处理，否则只是普通的任务拆分。
* **子问题相互独立**：同一个子问题不会被重复求解。若子问题大量重叠，分治会反复计算同一批状态，应改用动态规划。
* **规模确实缩小**：分解后的每个子问题都严格小于原问题，递归才能终止。
* **合并的代价可控**：如果合并比重新计算还昂贵，分解就没有收益。

### 与递归、动态规划的关系

分治描述“怎么分解、怎么合并”，递归是常见的实现方式；两者不是同义词。动态规划也常写成递推式，但它会保存子问题的答案。判断时先看子问题是否重叠：重叠就用动态规划，不重叠再考察分治的合并是否划算。

### 代价的估计

分治不保证更快。寻找最小值无论用循环还是分治，都至少检查每个元素一次；归并排序的收益来自“合并两个有序列表”这一步，代价是 $O(n\log n)$ 的时间和 $O(n)$ 的额外空间。分析时分别估计分解、递归调用和合并的工作量，不要只数递归调用的层数。

[来源：分治法](/knowledge/cs/algorithms/divide-and-conquer/#conditions)

5.3的四种写法都建立在这些条件上。贪心与动态规划的分界也在这里：子问题重叠时换策略，子问题分离时讨论合并的代价。

## 学习安排

5.1用找假币说明计算思维；5.2用递归加法、汉诺塔和归并熟悉基线条件与递归步骤；5.3把递归用于分治，比较寻找最小值的三种写法，再处理同时求最值、归并排序和二进制加法。5.4–5.6转到另外三类策略：贪心每步取局部最优，动态规划保存重叠子问题的答案，迷宫问题用回溯搜索。5.7用递归分解因数讨论问题复杂度，与5.1的“计算思维之美”首尾呼应。

阅读顺序上，递归在分治之前：分治的“求解”步骤就是递归调用。贪心与动态规划放在分治之后，便于比较“每一步都取局部最优”和“保存子问题答案”两种思路。

## 课程约定

* 本章用Python列表表示序列。切片`a[i:j]` 返回新列表，不会原地修改；递归函数常以`len(a) == 1`作为基线条件。
* 5.3的归并排序直接调用5.2定义的`merge`，教材没有在归并排序里重复实现它。
* 汉诺塔的`Hanoi(n, A, C, B)` 表示把 $n$ 个盘子从`A`移到`C`、以`B`为辅助柱。
* 二进制加法用`True`/`False`列表表示二进制位，列表首元素是高位。

## 方法选择

遇到算法设计题时，按下面的顺序判断：

1. 子问题是否重叠？重叠就考虑动态规划。
2. 每一步的局部最优能否推出全局最优？能证明就用贪心。
3. 能否分成独立的同型子问题并有效合并？可以就用分治。
4. 需要在多条路径中尝试、失败后回退？用回溯。

分治、贪心和动态规划都可能写成递归或递推。区别不在代码形式，而在子问题是否重叠、答案是否保存。

## 递归与动态规划的对比

> [!TIP]
> **同一个最长递增子序列问题的两种写法**
>
> 5.5先给出动态规划解法，再用一个直接递归的`Asc(k)` 版本对照。两个版本的状态含义相同：`Asc(k)` 都表示以`L[k]` 结尾的最长递增子序列长度。递归版按定义把`Asc(k)` 展开成对所有更小下标的调用，同一个`Asc(k)` 会被计算多次；动态规划版按`i`递增填表，让每个状态只算一次。子问题重叠时，这正是从递归改到动态规划的信号。

## 易错点

* 递归只写递归步骤、没有基线条件，或调用的规模没有变小，就无法终止。
* 分治要求子问题独立；子问题重叠时继续分治，会重复计算。
* 递归版求最小值与归并排序都用切片保存子列表，复制开销不能忽略。
* 贪心不是“每步取最大或最小”这么简单，需要证明局部最优能导向全局最优；币值任意的找零问题就可能失效。
* `Smin_max`合并时，最小值与最大值要分别处理，不能把两个返回值当成同一个量。

## 复习要点

5.7的`factors`先找出一个因数，再递归分解剩余部分，循环上界取 $\lfloor\sqrt{x}\rfloor$。它把5.1的“把问题拆成可计算步骤”和5.7的“复杂度”接在一起；复习时可以和找假币的线性扫描对照，比较两种做法把代价花在了哪里。