重新认识递归

递归是整个算法体系的底层基础设施——深度优先搜索、回溯、分治、动态规划的自顶向下写法，全部建立在递归之上。正确理解它，比记住任何具体算法模板都重要。

为什么先学递归

很多人对递归的印象是"不好理解"和"效率差"。这两个判断都是误解。

• 不好理解？ 递归是自顶向下的思路——你不需要知道从哪里开始，只需要定义"当前这一步该干什么"和"什么时候停"。相比手动维护栈和循环变量，递归其实更接近人对问题的自然拆分方式。
• 效率差？ 额外的函数调用开销在现代硬件上可以忽略。真正导致慢的原因是缺少记忆化或剪枝，与递归本身无关。

递归三要素

写出正确递归只需回答三个问题：

要素	问题	说明
函数签名	输入是什么、返回是什么？	定义子问题的接口
终止条件	什么时候停止递归？	也叫 base case，缺失或错误会导致栈溢出
递推关系	当前层如何用子问题的结果构造答案？	这一步写对了，递归就对了

把这三件事写清楚，不要试图在脑中展开每一层调用。信任递归——假设子调用已经返回了正确结果，你只需要处理当前层。这个思维方式被称为递归的信任跳跃（Leap of Faith）。

两种递归模式

绝大部分递归题目可以归入以下两类：

模式一：遍历（Traversal）

像遍历树一样走一遍所有节点，在遍历过程中用外部变量记录答案。

let result = 0;

function traverse(node: TreeNode | null): void {
  if (node === null) return; // base case
  // --- process current node ---
  result = Math.max(result, node.val);
  // --- recurse ---
  traverse(node.left);
  traverse(node.right);
}

特征：函数返回 void，答案靠外部变量收集。

模式二：分解（Decomposition）

把问题拆成子问题，让子调用返回结果，当前层汇总后再返回。

function maxDepth(node: TreeNode | null): number {
  if (node === null) return 0; // base case
  const left = maxDepth(node.left);   // trust sub-result
  const right = maxDepth(node.right); // trust sub-result
  return Math.max(left, right) + 1;   // combine
}

特征：函数有返回值，答案靠返回值层层汇总。

分解模式是回溯、分治、动态规划（自顶向下）的起点。当你给分解模式加上"选择 → 递归 → 撤销"的循环，它就变成了回溯；加上记忆化，它就变成了动态规划。

递归与其他专题的关系

递归
├─ + 遍历 / 路径记录 ─────→ DFS 深搜
├─ + 选择-递归-撤销 ──────→ 回溯
├─ + 独立子问题合并 ──────→ 分治
└─ + 重叠子问题 + 记忆化 ─→ 动态规划（Top-Down）

理解了递归，再学后面的专题时只是在递归骨架上增加约束或优化，不需要重新建立思维模型。

易错清单

1. 终止条件遗漏。最常见的栈溢出原因。写递归时第一件事就是写 base case。
2. 试图在脑中展开递归。这会让你越想越乱。只关注"当前层做什么"，信任子调用返回正确结果。
3. 该用分解模式却用了遍历模式。如果答案需要子问题的返回值来构造，就应该让函数有返回值，而不是用全局变量拼凑。
4. 忘记利用返回值。写了 return 却没在上层用 const sub = f(...) 接住，等于做了无用功。