递归与回溯
递归的基本写法，以及回溯搜索的通用框架。代码继续用 JavaScript。
1. 递归三要素（终止条件 / 递归关系 / 返回值）
递归：函数直接或间接调用自己。写对递归靠三件事：
| 要素 | 作用 |
|---|---|
| 终止条件 | 最小规模直接出答案，防止无限递归 |
| 递归关系 | 大问题怎么拆成更小的同类问题 |
| 返回值 / 副作用 | 子问题答案如何拼回，或写入结果集 |
// 阶乘：n! = n * (n-1)!
function factorial(n) {
if (n <= 1) return 1 // 终止
return n * factorial(n - 1) // 关系 + 返回
}
// 斐波那契（朴素，有重叠子问题，仅示意）
function fib(n) {
if (n <= 1) return n
return fib(n - 1) + fib(n - 2)
}
先用自然语言写清「规模 n 时依赖什么」，再落代码；终止条件要覆盖所有会走到的边界。
2. 递归与调用栈
每次调用压一帧（参数、局部变量、返回地址），返回时弹栈。深度太大 → 栈溢出。
// 深度 O(n)，n 很大时可能爆栈
function sum(n) {
if (n <= 0) return 0
return n + sum(n - 1)
}
// 可改成迭代，空间 O(1)
function sumIter(n) {
let s = 0
for (let i = 1; i <= n; i++) s += i
return s
}
分析复杂度时 ：
- 时间：看调用次数（斐波那契朴素是指数级）
- 空间：含最大栈深（二叉树递归最坏 O(n)，平衡时 O(log n)）
尾递归在部分语言可优化；JS 引擎一般不保证尾调用优化，深递归仍要小心。
3. 回溯框架（做选择 / 递归 / 撤销选择）
回溯 = 在解空间树上 DFS：试一条路径 → 到底或失败 → 撤销，试下一条。
function backtrack(路径, 选择列表) {
if (满足结束条件) {
记录(路径)
return
}
for (const 选择 of 选择列表) {
if (不合法) continue // 剪枝
做选择(路径, 选择)
backtrack(路径, 新的选择列表)
撤销选择(路径, 选择) // 关键：恢复现场
}
}
对应到代码，通常是：path.push → 递归 → path.pop。撤销漏了，后面的分支会被污染。
4. 排列 / 组合 / 子集
三类高频模板，差别在：是否可重复用、是否看顺序、起点怎么推进。
子集（选或不选，顺序不敏感）
function subsets(nums) {
const res = []
const path = []
function dfs(start) {
res.push(path.slice()) // 每个状态都是一个子集
for (let i = start; i < nums.length; i++) {
path.push(nums[i])
dfs(i + 1) // 只能选后面的，避免重复
path.pop()
}
}
dfs(0)
return res
}
组合（从 1..n 选 k 个，顺序不敏感）
function combine(n, k) {
const res = []
const path = []
function dfs(start) {
if (path.length === k) {
res.push(path.slice())
return
}
for (let i = start; i <= n; i++) {
path.push(i)
dfs(i + 1)
path.pop()
}
}
dfs(1)
return res
}
排列（顺序敏感，用 used 标记）
function permute(nums) {
const res = []
const path = []
const used = new Array(nums.length).fill(false)
function dfs() {
if (path.length === nums.length) {
res.push(path.slice())
return
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue
used[i] = true
path.push(nums[i])
dfs()
path.pop()
used[i] = false
}
}
dfs()
return res
}
| 问题 | 是否管顺序 | 下一层起点 | 去重手段 |
|---|---|---|---|
| 子集 | 不管 | i + 1 | start 递增 |
| 组合 | 不管 | i + 1 | start 递增 |
| 排列 | 管 | 仍从 0 扫 | used[] |
有重复元素时：先排序，再在同层跳过相同值（i > start && nums[i] === nums[i-1]）。
5. 剪枝
在进入递归前丢掉必败或必冗余分支，显著减枝。
// 组合总和：候选有序，剩余 target 已小于 candidates[i] 则可 break
function combinationSum(candidates, target) {
candidates.sort((a, b) => a - b)
const res = []
const path = []
function dfs(start, remain) {
if (remain === 0) {
res.push(path.slice())
return
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remain) break // 后面更大，剪掉
path.push(candidates[i])
dfs(i, remain - candidates[i]) // 可重复用：传 i；不可重复：传 i+1
path.pop()
}
}
dfs(0, target)
return res
}
常见剪枝：
- 可行性：当前已不可能合法（和已超、长度已不够）
- 最优性：已不优于已知答案（需要全局最优时）
- 对称 / 重复：同层相同选择只走一次
先保证正确，再加剪枝；剪枝条件必须「剪掉的一定无解」。
6. 与动态规划的关系（何时用回溯）
| 回溯 | 动态规划 | |
|---|---|---|
| 在做什么 | 枚举 / 搜索所有（或剪枝后的）路径 | 复用子问题最优解 |
| 典型输出 | 全部方案、任意一个方案 | 最优值 / 方案数 |
| 重叠子问题 | 常有大量重复计算 | 正是优化点 |
| 复杂度 | 往往指数级 | 多项式（若状态设计得好） |
何时用回溯：
- 要列出所有方案（排列组合、数独填空过程）
- 约束复杂，不好拆成简洁状态转移
- n 很小（如 ≤ 20），指数可接受
何时转向 DP / 其它：
- 只要最优值或方案数，且子问题重叠 → DP（见动态规划入门）
- 只要存在性且图论结构清晰 → BFS/DFS 图搜
- 贪心可证明最优 → 贪心
口诀：回溯负责「搜」，DP 负责「记」；记忆化搜索可以看成二者中间态（递归形式 + 缓存）。