递归与二叉树

怎么理解递归

递归难的不是写，是信

大多数人卡在递归上，不是因为不会写那几行代码，是因为忍不住在脑子里展开它—— reverse(head.next) 调用之后又调用 reverse(head.next.next)，展开到第三层就乱了。

这条路走不通，也不需要走。递归的正确用法是：写下函数的定义，然后相信这个定义。

三要素

任何一个递归函数都要先回答三件事：

  1. 函数定义 —— 它接收什么、返回什么？用一句话写清楚，写在注释里。
  2. base case —— 最小的情况是什么，直接返回什么？
  3. 递推关系 —— 假设更小的情况已经解决了，怎么用它得到当前的答案？

⭐ 顺序不能反。定义写不清楚，后面两条都无从谈起。 很多人跳过第一步直接写代码，然后在调试时才发现自己也说不清这个函数到底该返回什么。

例：递归反转链表

先写定义，一句话：

reverse(head) 接收一条链表的头结点，把整条链表反转，返回新的头结点。

有了这句话，代码几乎是抄出来的：

function reverse(head) {
  // base case：空链表或只剩一个节点，反转后还是它自己
  if (head === null || head.next === null) return head;

  // 相信定义：这一行之后，head.next 开始的那段已经反转好了
  const newHead = reverse(head.next);

  // 现在只需要处理 head 自己这一个节点
  head.next.next = head;
  head.next = null;

  return newHead;
}

关键是中间那一行的注释。执行完 reverse(head.next) 之后，后面那段是什么样子？ 按定义，它已经反转完了。你不需要知道它是怎么反转的。

原来是 head -> a -> b -> c，现在后半段变成 c -> b -> a， 而 a 仍然被 head.next 指着 —— 它现在是那段反转结果的尾巴。 所以 head.next.next = head 就是把 head 接到尾巴后面， 再 head.next = null 断开原来那根正向指针。

📌 注意 newHead 从头到尾没参与任何计算，只是原样往上传 —— 它是整条链表反转后的新头结点，在递归的最深处就定下来了， 中间每一层都只负责接好自己这一个节点。

「相信它能 work」不是玄学

这一条听起来像自我催眠，其实就是数学归纳法：

  • base case 正确（最小情况成立）
  • 假设 n - 1 时正确，能推出 n 时也正确

两条都成立，函数对所有 n 都正确。你在写递推关系时做的那个假设， 就是归纳法里的「假设 n - 1 成立」。

⚠️ 所以真正需要检查的只有两处：base case 对不对， 以及递推那一步有没有偷偷假设了比 n - 1 更多的东西。 展开到第三层去手动模拟，检查的是执行过程 —— 而执行过程不是你需要保证的东西。

递归树怎么读出复杂度

时间复杂度不看代码，看递归树：

时间复杂度 = 递归树的节点总数 × 每个节点自己做的事

反转链表的递归树是一条链：n 个节点，每个节点做 O(1) 的指针操作， 所以是 O(n)。空间复杂度是递归深度，也是 O(n) —— 每一层都在调用栈上占一个帧。

⭐ 这个「节点数 × 每节点耗时」的算法对所有递归都适用。

⚖️ 朴素斐波那契是 O(2ⁿ) 吗：是上界，但不是它的增长速度

流行的说法是「递归树近乎满二叉树，所以 O(2ⁿ)」。数一下实际调用次数：

n 实际调用次数 2ⁿ 调用次数 / 2ⁿ
10 177 1.0×10³ 0.173
15 1,973 3.3×10⁴ 0.060
20 21,891 1.0×10⁶ 0.021
25 242,785 3.4×10⁷ 0.007
30 2,692,537 1.1×10⁹ 0.003

⚠️ 最后一列一路下降。如果真是 Θ(2ⁿ)，这个比值该收敛到一个正数才对。

真实的关系可以精确写出来：调用次数 = 2·F(n+1) − 1。 n = 25 时 2 × 121393 − 1 = 242785，与实测逐位相同。

⭐ 所以增长的底数是黄金比 φ ≈ 1.618，不是 2。实测相邻比值也印证了： n 每加 5，调用次数乘 11.09（= φ⁵）；每加 2，乘 2.618（= φ²）。

📌 「O(2ⁿ)」作为上界没说错（φ < 2），只是不紧。面试说 O(2ⁿ) 不会被扣分， 但知道它其实是 Θ(φⁿ) 能解释一件事：为什么 n=40 还能跑出来（φ⁴⁰ ≈ 2.3×10⁸， 而 2⁴⁰ ≈ 1.1×10¹²，差四个数量级）。

递归树里大量节点在算同一个子问题 —— 把重复的剪掉就是 动态规划。同样是 n = 32：

朴素递归    7,049,155 次调用
记忆化             63 次调用      → 111891×

什么时候会栈溢出

递归深度受调用栈大小限制，超过就是 RangeError: Maximum call stack size exceeded。

🚨 「大约一万层」不是一个数

二分探测实测（Node v22.22.3 / V8 12.4）。 ⚠️ 每种写法必须各起一个进程 —— 同一进程里连测几种，后测的会白蹭前面攒下的 JIT 状态，量出来的数会一路变大：

                              隔离进程，各测三次
最简递归（每帧只有一个参数）      9253 / 9253 / 9375
每帧多几个局部变量                6446 / 6446 / 6446
上面那个反转链表的递归            7911 / 7911 / 7911

⭐ 隔离之后每种写法自己非常稳（三次几乎一模一样）， 而三种之间差了 1.4 倍 —— 差别来自每帧多大，这一条是可靠的。

⚠️ 但同一个进程里反复探测同一个函数，这个数会一路涨到饱和：

第 1 次   9375
第 2 次起  10982    （之后 6 次全部一样）

⭐ 差 1.17 倍，原因是 JIT：冷启动时函数跑在解释器里，栈帧大； 被优化编译之后帧变小，同样的栈能装下更多层。

🚨 所以这一节里任何一个具体数字都不值得记住。 它同时取决于 每帧多大、函数有没有被优化过、以及你是不是在同一个进程里量过别的东西。 👉 要记的是量级：六千到一万一。写代码时按下限估，别按上限。

处理真实数据时不够

递归版反转 100000 个节点   RangeError: Maximum call stack size exceeded
迭代版反转 100000 个节点   正常

算法题的数据规模常在这个坎附近（力扣链表题到 5×10⁴）， 所以递归版在真题上就可能崩，不是只有「真实数据」才会。

⚠️ 别指望尾递归优化救你

ES2015 规范里确实有尾调用优化（TCO），但主流引擎没有实现（Safari 是例外）。 把代码改写成尾递归形式，在 V8 上照样溢出 —— 实测：

const tail    = (n, acc = 0) => n === 0 ? acc : tail(n - 1, acc + n);  // 严格尾调用
const nonTail = (n) => n === 0 ? 0 : n + nonTail(n - 1);               // 加法在返回后
              冷启动（全新进程首次调用）   反复探测到饱和
尾递归形式              6105                  7845
非尾递归                7850                 10984
                                             ↑ 两者差 28.6%，始终不同

尾递归跑 100 万层   RangeError: Maximum call stack size exceeded

🚨 真有 TCO 的话，尾递归应该根本不受栈深度限制（能跑到千万级）。 实测它撑到七千多就崩 —— TCO 完全没有生效。

⭐ 而且证据比「和非尾递归一样」更强：尾递归比非尾递归还浅 28.6%。 多带的那个 acc 参数让每帧变大了，如果 TCO 生效，帧根本不该累积。

⚠️ 注意冷启动和饱和后方向一致（6105 < 7850，7845 < 10984）—— 这个差是真实的帧大小差异，不是 JIT 伪影。 📌 但两列的绝对值差了 1.3~1.4 倍，所以拿「栈能撑多少层」做任何对比， 都得先确认两边的预热状态一样 —— 上一节那个 1.17 倍的 JIT 效应， 在这里换了个马甲又出现了一次。

📌 这是一个「按规范该成立、按实现不成立」的陷阱，而报错信息不会告诉你这一点 —— 你会以为是自己没写对尾调用形式，然后在那上面浪费时间。

👉 判据：递归深度与输入规模同阶时（链表、退化成链的树），心里要有这根弦； 深度是 O(log n) 时（平衡树、二分）不用担心。后半句也实测过：

递归建一棵 100 万节点的平衡树 + 递归求深度    正常，树高 20
递归建一棵 1000 万节点的平衡树 + 递归求深度   正常，树高 24

⭐ 一千万个节点，递归深度只有 24 —— 离六千那个下限差 325 倍。 O(log n) 的深度是真的安全，不是「小心一点应该没事」。 📌 这也是全篇唯一一个不用管上面那堆测量条件的结论： 差两个数量级的时候，JIT、帧大小、预热状态全都无所谓。

下一步

递归讲清楚之后，二叉树是它最自然的用武之地 —— 也是整个教程的枢纽：后面的回溯、DFS、分治、动态规划、BFS，全是二叉树递归的变形。

练习

勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。