一、课上练习

编程练习

1. 自然数的分解：L3091

二、知识总结

✨ 核心思想

递归搜索是一种通过分治法解决问题的编程技术，它通过将大问题分解为更小的、相同类型的子问题来工作。递归函数会调用自身来解决这些子问题，每次调用通常都会使问题的规模减小，直到达到一个基本情况（基案/停止条件），此时无需进一步的递归调用。

递归搜索在算法设计中应用广泛，尤其适合那些具有天然递归结构的问题，如树的遍历、图的搜索、排列组合等。

✨ 递归搜索的关键要素

递归搜索包含两个核心要素：

• 基案（Base Case）：这是停止递归的条件。如果没有基案，递归可能会导致无限循环或堆栈溢出错误。通常，基案处理问题的最小可能分割，例如在搜索算法中找到一个特定值或达到搜索空间的边界。
• 递归步骤（Recursive Step）：这是函数调用自身的部分，目的是将问题规模缩小向基案靠近。在每次递归调用中，传入的参数应体现问题规模的缩小，例如减少数组的大小、降低数值等。

✨ 实现递归搜索的注意事项

在实现递归搜索时，需要注意以下几个问题：

• 堆栈溢出：递归调用深度过大可能导致堆栈溢出。可以通过限制递归深度或使用迭代版本来避免。
• 重复计算：某些递归问题可能多次计算相同的子问题。使用缓存机制（如备忘录或动态规划技术）可以避免重复计算，提高效率。
• 递归到迭代：有时，可以将递归逻辑改写为迭代形式以提高效率和避免堆栈溢出。

✨ 常见的递归搜索类型

深度优先搜索（DFS）

用于图和树的遍历。从一个节点开始，尽可能深地探索节点的分支，直到所有路径都被探索为止。适用于需要访问图中所有节点的场景，如解决迷宫问题或游戏的解决策略。

回溯算法

是一种通过递归来试探和错误回退的搜索算法，用于解决约束满足问题。当一个分支的选择最终导致解决方案不可行时，算法会退回一步，尝试另一个选项。常用于排列、组合、分区问题，例如八皇后问题、图着色问题等。

二分查找

在有序数组中查找特定元素的技术。每次递归调用选择中点，并根据中点与目标值的比较结果决定是继续在左侧还是右侧子数组中搜索。这种方法大大减少了搜索的规模，具有对数时间复杂度。

✨ 执行示例

以"将自然数 4 分解为若干正整数之和"为例，展示递归搜索的完整过程。

要求输出所有分解方案（每个方案中的数字从小到大排列），如 4 = 1+1+1+1 = 1+1+2 = 1+3 = 2+2 = 4。

递归函数设计：dfs(剩余值, 当前最小可用值)

1dfs(4, 1) — 剩余4，从1开始选
2├── 选1 → dfs(3, 1) — 剩余3，从1开始选
3│   ├── 选1 → dfs(2, 1) — 剩余2，从1开始选
4│   │   ├── 选1 → dfs(1, 1) — 剩余1，从1开始选
5│   │   │   └── 选1 → dfs(0, 1) — 剩余0，输出：1+1+1+1
6│   │   └── 选2 → dfs(0, 2) — 剩余0，输出：1+1+2
7│   ├── 选2 → dfs(1, 2) — 剩余1，从2开始选，无合法选择，回退
8│   └── 选3 → dfs(0, 3) — 剩余0，输出：1+3
9├── 选2 → dfs(2, 2) — 剩余2，从2开始选
10│   └── 选2 → dfs(0, 2) — 剩余0，输出：2+2
11├── 选3 → dfs(1, 3) — 剩余1，从3开始选，无合法选择，回退
12└── 选4 → dfs(0, 4) — 剩余0，输出：4

最终输出 5 种分解方案。注意"从当前最小可用值开始选"这个约束保证了每种方案中的数字是非递减的，避免了重复方案（如 1+3 和 3+1 只输出一次）。

✨ 解题步骤详解

设计递归搜索解法时，按以下步骤思考：

1. 定义状态：确定递归函数的参数代表什么。通常包括"当前处理到哪一步"和"约束条件"。例如上例中用"剩余值"和"最小可用值"来定义状态。
2. 确定基案：什么时候递归结束？通常是"完成了所有选择"或"剩余为零"。基案中通常需要输出或记录答案。
3. 确定选择：在每一步有哪些合法的选择？用循环枚举所有可能。
4. 递归调用：做出选择后，用更新后的参数调用自身，处理更小的子问题。
5. 剪枝优化：如果可以提前判断某个分支不可能产生合法解，直接跳过，减少搜索量。例如上例中"剩余值 < 最小可用值"时直接回退。

✨ 常见错误

• 缺少基案或基案条件不正确：会导致递归永不结束或漏掉部分答案。
• 忘记"撤销选择"：如果使用全局数组记录路径，做完递归后要撤销当前选择（回溯），否则会影响后续分支的搜索。
• 重复搜索：没有合理设置起始值，导致同一组合被多次枚举。例如分解问题中如果不限制"当前最小可用值"，1+3 和 3+1 会被当成两个不同方案。
• 递归参数传递错误：特别是"传值"和"传引用"的区别。如果用全局变量或引用传递，修改后会影响其他分支。
• 搜索空间爆炸：如果问题规模较大且没有有效剪枝，搜索时间会指数级增长。遇到这种情况要先分析是否有更好的算法（如动态规划）。

三、课后练习

编程练习

1. 自然数的拆分：L3092