递归与分治 - 算法与数据结构教程

讲解

递归是函数调用自身来解决问题的写法，它的正确性建立在「把大问题拆成同构的小问题」上。写递归有公认的三个要素：终止条件（什么时候不再递归）、递推关系（大问题如何由小问题的答案组合出来）、以及一个隐含要素——递归规模必须严格缩小，否则永不终止。写递归函数时不要在脑子里模拟整个调用栈（人脑栈深不够），而是「相信递归」：假设子问题的调用已经正确返回，只专注本层的组合逻辑。

斐波那契是理解递归的第一课，也是理解递归缺陷的第一课。朴素的 fib(n) = fib(n-1) + fib(n-2) 存在大量重复计算：fib(n-2) 会被 fib(n-1) 和本层各算一次，调用树指数膨胀，时间 O(2ⁿ)。解法是给递归加「记忆」——用 Map 缓存已算过的结果（记忆化搜索），时间立刻降到 O(n)。这条「递归 + 记忆化」的路再往前走一步、把自顶向下换成自底向上的递推，就是动态规划（后面有两章专讲）。

分治（divide and conquer）是递归最规整的应用形态：拆成若干规模减半的子问题、递归求解、合并结果。归并排序是它的标准像（排序一章会完整实现），快速幂 Pow(x, n) 是它的小品版：xⁿ = (x^(n/2))²，每次把指数减半，O(log n) 次乘法搞定。汉诺塔则展示递归的表达力：n 盘问题 = 先把 n-1 盘移到辅助柱、移底盘、再把 n-1 盘移回来——三行递归描述了一个手工要 2ⁿ-1 步的过程。

示例

三个代表：记忆化斐波那契、快速幂、汉诺塔（返回每一步的移动记录）：

import assert from 'node:assert/strict';

function fib(n) {
  const memo = new Map();
  function go(k) {
    if (k <= 1) return k; // 终止条件
    if (memo.has(k)) return memo.get(k); // 命中缓存，砍掉整棵子树
    const v = go(k - 1) + go(k - 2);
    memo.set(k, v);
    return v;
  }
  return go(n);
}

// 快速幂：exp 每次减半，O(log n) 次乘法
function myPow(x, n) {
  function go(base, exp) {
    if (exp === 0) return 1;
    const half = go(base, Math.floor(exp / 2));
    return exp % 2 === 0 ? half * half : half * half * base;
  }
  return n >= 0 ? go(x, n) : 1 / go(x, -n);
}

// 汉诺塔：把 n 个盘从 from 经 via 移到 to，记录每一步
function hanoi(n, from, to, via, moves) {
  if (n === 0) return;
  hanoi(n - 1, from, via, to, moves); // 上面 n-1 盘先让位
  moves.push([from, to]); // 移底盘
  hanoi(n - 1, via, to, from, moves); // n-1 盘归位
}

assert.strictEqual(fib(10), 55);
assert.strictEqual(fib(50), 12586269025); // 记忆化让大 n 也瞬间完成

assert.strictEqual(myPow(2, 10), 1024);
assert.strictEqual(myPow(2, -2), 0.25);
assert.ok(Math.abs(myPow(2.1, 3) - 9.261) < 1e-9);

const moves = [];
hanoi(3, 'A', 'C', 'B', moves);
assert.strictEqual(moves.length, 7); // 2^3 - 1
assert.deepStrictEqual(moves[0], ['A', 'C']);
assert.deepStrictEqual(moves[6], ['A', 'C']);

console.log('3 盘汉诺塔最少步数:', moves.length);
console.log('递归与分治示例全部通过');

留意 myPow 对负指数的处理：先算正指数再取倒数，把负数情形归约掉——「把边界情形归约到已解决的情形」也是递归设计里的常用手法。

常见坑

忘记终止条件或条件不可达：递归规模必须严格向终止条件收敛；fib(n) 写成 go(k-1)+go(k-2) 而终止只判 k===0，负数就永远停不下来。
在脑中展开整个调用栈：人脑模拟三层以上必然出错；用「相信子调用」的方式思考，必要时画两层验证。
重复计算不加记忆化：朴素递归斐波那契在 n=50 时已经算不动；写递归前先数一遍「子问题会不会重复出现」。
递归深度失控：链式递归（每层只减 1）在 n 很大时爆栈（JS 默认约一万层）；能改写循环就改写，或确认数据规模安全。
快速幂把 exp/2 写成分数：Math.floor 不可省，JS 的 / 产生浮点数，指数必须是整数才能正确终止。

小结

递归三要素：终止条件、递推关系、规模严格缩小；思考时「相信递归」只写本层逻辑；重复计算用记忆化；分治 = 拆半 + 递归 + 合并。下一章把「拆半」用到极致：二分查找。