递归搜索是一种通过分治法解决问题的编程技术，它通过将大问题分解为更小的、相同类型的子问题来工作。递归函数会调用自身来解决这些子问题，每次调用通常都会使问题的规模减小，直到达到一个基本情况（基案/停止条件），此时无需进一步的递归调用。
递归搜索在算法设计中应用广泛，尤其适合那些具有天然递归结构的问题，如树的遍历、图的搜索、排列组合等。
递归搜索包含两个核心要素：
在实现递归搜索时，需要注意以下几个问题：
用于图和树的遍历。从一个节点开始，尽可能深地探索节点的分支，直到所有路径都被探索为止。适用于需要访问图中所有节点的场景，如解决迷宫问题或游戏的解决策略。
是一种通过递归来试探和错误回退的搜索算法，用于解决约束满足问题。当一个分支的选择最终导致解决方案不可行时，算法会退回一步，尝试另一个选项。常用于排列、组合、分区问题，例如八皇后问题、图着色问题等。
在有序数组中查找特定元素的技术。每次递归调用选择中点，并根据中点与目标值的比较结果决定是继续在左侧还是右侧子数组中搜索。这种方法大大减少了搜索的规模，具有对数时间复杂度。
以"将自然数 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 只输出一次）。
设计递归搜索解法时，按以下步骤思考：