企业官网建设流程全解析

算法分析这件事，我最常听到的一句话是：“递归的代码我能看懂，一问时间复杂度就答不上来。”尤其是刷题遇到那种递归解法，题目能 AC，别人问“你这段代码是 O(n) 还是 O(n log n)？”就支支吾吾了。老实说，递归的复杂度分析在算法学习里是最容易“看着懂、一算错”的部分。它不像循环那样一眼数出层数，因为递归的时间和空间开销藏在函数调用的堆叠里，你光看代码看不出到底跑了多少步。

这篇文章就是来把这层窗户纸捅破的。我会从递归的核心结构讲起，把时间复杂度的三种分析方法（递归树、主定理、代换法）讲透，再把空间复杂度里最容易被人忽视的调用栈问题单独拎出来说，最后用阶乘、斐波那契、归并排序、二分查找这四个经典案例把整个分析过程走一遍。适合正在准备面试、学算法数据结构会卡壳、或者写递归老担心性能问题的读者。看完之后你再碰到递归问题，应该能条件反射地把复杂度说出来。

1. 递归复杂度分析到底在分析什么：先搭好三个底层概念

很多人在分析递归复杂度时翻车，不是因为数学不行，而是因为在动手之前没有把递归这件事本身想清楚。递归不是魔法，它只是把一个大规模问题拆成若干个相似的小规模问题，层层递进，直到小到可以直接返回。复杂度分析的本质，就是搞清楚整个“拆解—递进—回溯”的过程总共产生了多少计算开销、占用了多少运行环境资源。

1.1 递归的本质是问题分解，复杂度来自“子问题的堆叠”

把递归想象成剥洋葱。你要知道最里面那层是什么，就必须先剥掉外面一层，而每剥一层都有一层壳要处理。如果你定义的递归函数每次只剥掉一层壳，处理这层壳本身的开销是 O(1)，那么剥完 n 层洋葱的时间就是 O(n)——这就是线性递归。如果每剥掉一层洋葱，剩下的部分还能再拆成两半，每一半还要继续剥，那这个开销就变成指数级——因为你剥到一半会发现要同时处理越来越多的半颗洋葱。

这个类比想说明一件事：递归复杂度的量级，取决于“问题规模的缩小速度”和“子问题的数量”这两个变量的组合。每次递归把一个规模为 n 的问题变成规模为 n-1 的问题，子问题数量是 1，那总工作量大多时候是 O(n)；每次把规模为 n 的问题拆成两个 n/2 的子问题，子问题数量是 2，总工作量就有机会控制在 O(n log n)；每次拆成两个 n-1 的子问题，子问题数量是 2 且规模缩减缓慢，那就会走向 O(2^n) 的深渊。

所以在分析之前，先别看代码行数，先回答三个问题：

1. 递归函数每次把问题规模缩到原来的几分之一（或者减多少）？
2. 每次递归会产生几个子问题？
3. 除了子问题的递归调用之外，当前这层还要做多少额外工作（合并、比较、遍历）？

把这三个问题答清楚，复杂度的框架基本就出来了。后面做的所有计算，都只是给这个框架补上精确的量级而已。

1.2 统一递推式 T(n) = aT(n/b) + f(n)：看懂三个参数的直觉

算法导论里把递归的规模变化写成标准形式：

T(n) = aT(n/b) + f(n)

其中：

• n 是当前问题的规模；
• a 是递归调用产生的子问题个数；
• n/b 是每个子问题的规模（大致上每个子问题是原问题的 b 分之一）；
• f(n) 表示除了子问题递归之外，本层还要做的其他工作，比如合并两个有序数组的开销是 O(n)，比较一个数字的开销是 O(1)。

这个式子里的三个参数，正好对应刚刚提到的三个问题。a 和 b 决定了递归树的形状，f(n) 决定了每一层要额外付出多少代价。整个时间复杂度的分析，本质上就是在比较“递归产生的总开销”和“每一层额外工作累加的开销”到底哪个更大。

这里要强调一点：并不是所有的递归都能写出经典的递推式。比如斐波那契数列的朴素递归，子问题规模是 n-1 和 n-2，它们不是严格的 n/b 形式，这时候硬套递推式会很不舒服，递归树反而更好用。所以我的习惯是：先尝试写递推式，如果写不出来标准形式，就转用递归树。后面第 2 节、第 4 节都会演示这两种方式的切换。

1.3 时间与空间的纠缠：递归是怎么同时吃掉 CPU 和内存的

递归和时间复杂度、空间复杂度之间有一种天然纠缠：每次递归调用都会在调用栈上压入一个栈帧，里面保存着返回地址、参数值、局部变量。递归没返回之前，这一层的栈帧不会释放。

举一个最生活化的例子。你在公司里给下属布置任务，下属又层层往下布置，最底层的员工干活，然后一层层往上汇报。期间每一层负责人都在等待结果，都需要“挂起”在那里。挂起的这些负责人不会干活，但他们占着位子、占着会议室、算力被无效占用。递归的空间复杂度，就是你同时挂起了多少层负责人；递归的时间复杂度，是整条任务链上所有人实际付出的等待和计算的总和。

这个视角非常重要，因为很多人在分析空间复杂度时犯的一个典型错误，是只数函数里声明了几个变量。实际上递归的空间消耗主要是调用栈的深度，函数内部的局部变量只是栈帧的一部分。所以在分析空间复杂度前，先想清楚“最深的时候我同时嵌套了多层递归”，再往下计算。

2. 时间复杂度的三种实用解法：递归树、主定理、代换法

有了递推式的基础之后，接下来就是真正动手算复杂度。我平时最常用的方法就三种：递归树、主定理、代换法。它们的适用场景不太一样：递归树适合“眼见为实”，把每一层开销画出来再求和；主定理适合标准形式的快速判断，能几秒钟出答案；代换法适合证明上界，尤其是复杂递推式的渐进分析。

2.1 递归树怎么画、怎么求和（含叶节点坑）

递归树是分析递归复杂度最直观的工具。以 T(n) = 2T(n/2) + n 为例，画法分三步：

第一步：画根节点。根节点代表规模为 n 的完整问题，节点旁边的值写上本层额外工作，也就是 f(n) = n。

第二步：画子节点。从根节点分出 a 个子节点，每个子节点规模是 n/b。上例中 a=2、b=2，所以画两个子节点，每个规模 n/2，每个子节点额外工作 n/2，两个合计 n。

第三步：继续往下展开，直到规模缩小到 1。记录每一层的“总工作量”。第一层是 n，第二层是 n（因为两个 n/2 加起来还是 n），第三层是 4 个 n/4，加起来还是 n。树的高度是 log₂n，所以总工作量是 n × log₂n。

用代码来表示这个求和过程：

T(n) = n + 2*(n/2) + 4*(n/4) + ... + 2^(k-1) * (n/2^(k-1)) + 叶节点开销 = n + n + n + ... (共 log₂n 层) + 叶节点数量 = nlog₂n + n

最终 T(n) = O(n log n)。

这里有个特别容易踩的坑：很多人画完“非叶子层”的开销就停了，忘了算最后一层叶节点的开销。叶节点是规模为 1 的子问题，它们也要对应一次基本操作或者说返回操作。如果每一层额外工作正好趋近于常数，那叶节点的数量级就必须单独估算。比如 Fibonacci 那种满二叉树，叶子节点数量占整个节点总数的很大比例，不算叶子会直接导致结果差一个数量级。

我还想分享一个递归树加速技巧：当每一层的额外工作量不相等时，不要急着逐层精算，先观察层与层之间的变化趋势。是等比增长、等差增长，还是等比衰减？等比衰减时总和无非就收敛到一个常数倍的首项，等比增长时则后一层决定总量。这个“看趋势”的习惯能帮你省下大量笔算时间。

2.2 主定理三情形：一张表、三条路

主定理（Master Theorem）是解决标准分治递归的利器。只要递推式能写成 T(n) = aT(n/b) + f(n)，其中 a≥1、b>1，就能套用。它的核心思想是拿 f(n) 和 n^(log_b a) 比大小，那个“谁更大，复杂度就由谁决定”。更精确地说：

这么说可能还是抽象，我换成人话：

• 如果 n^(log_b a) 明显比 f(n) 大，说明递归本身的开销占主导。
• 如果两者差不多大，说明递归开销和每层额外工作“势均力敌”，结果要在外面多乘一个 log n。
• 如果 f(n) 明显比 n^(log_b a) 大，说明每层的额外工作才是主角，复杂度由 f(n) 决定。

举两个高频例子。

归并排序：T(n) = 2T(n/2) + O(n)。这里 a=2、b=2，所以 n^(log₂2) = n。而 f(n) = n，两者同阶，对应情形 2。结论：T(n) = Θ(n log n)。

二分查找：T(n) = T(n/2) + O(1)。这里 a=1、b=2，n^(log₂1) = 1，f(n) = O(1)，两者同阶，情形 2。结论：T(n) = Θ(log n)。

注意，主定理的“正则条件”在情形 3 里很容易被人忽略。这个条件的含义是：子问题的开销加起来不能超过当前层开销的一个固定比例，否则递归树可能出现某一层的开销不降反增，导致最终复杂度无法收敛。大多数情况下你不需要死磕这个条件，直接套结论就行，但遇到奇怪的 f(n)（比如 n/log n 这种非多项式形式）时，要记得检查。

另外要提醒的是，主定理不适用于 T(n) = T(n-1) + T(n-2) + O(1) 这种“规模不是等比例缩小”的递归，这时候递归树才是更靠谱的路径。有些面试者一上来就背主定理，碰到 Fibonacci 就翻车，原因就在这。

2.3 代换法：先猜后证，怎么确定 c 和 n0

代换法主要用于证明。过程很简单：先猜一个上界，再用数学归纳法证明。难的地方其实在“猜”，猜错了后面全白做。

以 T(n) = 2T(n/2) + n 为例，我猜 T(n) = O(n log n)。要证明它，需要证明存在常数 c>0 和 n₀>0，使得对所有 n≥n₀ 有 T(n) ≤ c·n·log₂n。

归纳证明的步骤是这样：假设 T(k) ≤ c·k·log₂k 对于所有 k<n 成立，然后代入原递推式：

T(n) ≤ 2[c·(n/2)·log₂(n/2)] + n = c·n·(log₂n - 1) + n = c·n·log₂n - c·n + n

为了让上式 ≤ c·n·log₂n，只需要 -c·n + n ≤ 0，即 c≥1。通常我取 c=2，再补上边界条件检查，就能完成证明。

这个证明过程中有一个细节值得记住：别把 log 的底数太当回事，因为不同底的对数只差一个常数倍，不影响渐进量级。我在实际做题时，经常直接用自然对数或者干脆不写下标，把证明写得更清爽，最后在结论里补一个“不同底数差常数倍”就完事。

代换法还有个“加强猜想”的技巧。有时候直接猜 T(n) ≤ c·n·log₂n 会因为常数项卡住，这时候改成猜 T(n) ≤ c·n·log₂n - d·n（多减一个低阶项），反而更容易凑出不等式。这个技巧我在分析快速排序的期望复杂度时用过很多次，非常实用。

3. 空间复杂度的正确算法：调用栈深度才是关键

聊完时间，再聊空间。递归空间复杂度的最大误区，就是只看局部变量个数。真正决定递归空间量级的是两个量：递归的最大深度、单层栈帧的大小。这两个量相乘，才是递归的空间开销。

3.1 每层递归都有一份“帧”开销

每次函数调用，系统都会往调用栈里压入一个栈帧。栈帧里保存了：

• 调用者的返回地址；
• 函数参数（如果是传值调用，参数会被复制一份）；
• 函数内部的局部变量；
• 一些保存寄存器状态的内容。

所以就算你的函数里只声明了一个 int，每次递归调用也会产生至少几十字节的固定开销。在分析渐进复杂度时，常数量级不用太纠结，关键是搞清楚“递归最多嵌套多少层”。

比如阶乘递归：

function fact(n) { if (n <= 1) return 1; return n * fact(n - 1); }

这个递归每调用一层，问题规模减 1，所以最大递归深度是 n。每层的栈帧大小是常数 O(1)，空间复杂度就是 O(n)。虽然从代码上看局部变量只有一个参数 n，但实际空间开销随着 n 线性增长，原因就在于栈深度。

3.2 空间复杂度公式：帧大小 × 栈深度

把上面的逻辑公式化：

递归空间复杂度 = 最大递归深度 × 单层栈帧大小

最大递归深度通常等于递归树从根到最远叶子节点的路径长度，而不是递归树的节点总数。这一点特别容易被搞混。有人看到 Fibonacci 朴素递归的递归树节点数是指数级的，就以为空间复杂度也是指数级。但实际上，函数调用是“先深入最深的一层，再一层层返回”的，任何一个时刻栈里只有一条从根到叶子的路径，不是整棵树的全部节点同时存在。

所以 Fibonacci 朴素递归虽然时间 O(2^n)，但空间只是 O(n)。这就是为什么“时间爆炸而空间还好”的现象在树形递归里很常见。同样，分治算法比如归并排序，递归树深度是 log n，不计算额外辅助数组的话，递归这部分的空间复杂度是 O(log n)，而不是 O(n log n)。

3.3 尾递归、迭代改写与空间优化

空间复杂度经常把程序逼到墙角，最常见的优化手段就是尾递归改写。

先看尾递归长什么样。普通递归：

function sum(n) { if (n === 0) return 0; return n + sum(n - 1); }

这个函数 return 里还带着n + sum(n-1)，也就是说当前帧必须等更深层的 sum 返回之后，还要再执行一次加法，所以当前帧不能提前释放。空间复杂度 O(n)。

改成尾递归：

function sumTail(n, acc) { if (n === 0) return acc; return sumTail(n - 1, acc + n); }

递归调用发生在 return 语句的最后位置，而且调用结果不再参与任何额外的运算。如果语言编译器支持尾递归优化（Tail Call Optimization），当前帧就可以直接替换成新帧，空间复杂度降为 O(1)。但这里有个残酷的现实：大部分主流语言（比如 Python、Java）默认不支持尾递归优化，把这个“优化”写进面试答案时一定要先问清楚语言环境，否则会被面试官追问到细节上。

在没有尾递归优化的语言里，想把空间压下来，最稳妥的办法就是直接用栈模拟递归。比如把递归树的遍历改成显式栈的迭代版本，空间能精确控制，只是代码可读性会下降。这也是我在工程里经常做的事：先把递归版写对，再在性能瓶颈处改成显式栈版本。优缺点很分明——递归好懂、利于维护，空间可能爆；迭代省空间、更快，但逻辑绕。到底选哪个，等看到第 5 节的原则再加工程视角综合判断。

4. 经典案例四连拆：从简单递归到分治递归

前面理论说得再多，不落到具体案例上，总觉得飘。这一节我选了四个经典递归，从最简单到最复杂，逐个拆解时间复杂度和空间复杂度。这四个案例也恰好覆盖了线性递归、树形递归、分治递归、尾递归化之后的最典型形态。

4.1 案例一：阶乘——线性递归的时间与空间

先看最经典的阶乘。递归写法：

function fact(n) { if (n === 1) return 1; return n * fact(n - 1); }

递推式直接写出来：

T(n) = T(n-1) + O(1)

每次递归只产生 1 个子问题，规模减 1，额外工作是常数。把递归式逐层展开：

T(n) = T(n-1) + 1 = T(n-2) + 2 = ... = T(1) + (n-1) = O(n)

时间复杂度 O(n)，没有任何悬念。空间复杂度，最大递归深度为 n，每层栈帧 O(1)，所以也是 O(n)。这就是典型的线性递归：时间、空间都是线性增长。

如果想优化空间，可以改成尾递归写法：

function factTail(n, acc) { if (n === 1) return acc; return factTail(n - 1, acc * n); }

在支持尾递归优化的编译器下，空间复杂度可以降到 O(1)。不过在 JavaScript 里，只有严格模式下才保证尾调用优化，这一点容易被忽略。

4.2 案例二：斐波那契朴素递归——指数时间的真相

斐波那契数列的朴素递归是所有递归分析里的“重灾区”：

function fib(n) { if (n <= 2) return 1; return fib(n - 1) + fib(n - 2); }

很多人一眼看到“每次调用会再产生两个调用”，就直接说 O(2^n)。这个结论对量级方向没错，但不够精确。我先说标准递推式：

T(n) = T(n-1) + T(n-2) + O(1)

这个递推式不能用主定理，因为子问题规模不是等比例缩小。我们用递归树来分析。树的根是规模 n，往下第一层两个节点 n-1、n-2，第二层产生 4 个节点，以此类推。第 k 层大约有 2^k 个节点，规模大约为 n-k。层数从 0 到 n-2 左右。所以节点总数近似：

第0层: 1 第1层: 2 第2层: 4 ... 第n-2层: 2^(n-2)

总和约等于 2^(n-1) - 1，所以时间复杂度是 O(2^n)。如果求精确点，斐波那契递归的实际复杂度是 Θ(φ^n)，其中 φ 是黄金比例约 1.618。我面试时习惯先说 O(2^n)，然后补一句“更精确地说是 Θ(φ^n)，因为每层实际节点数增长速率接近 φ 而不是 2”，这一个补充往往能让面试官刮目相看。

空间复杂度就要小心了。虽然递归树节点很多，但任意时刻调用栈里只存在一条路径。深度最深时走的是 n → n-1 → n-2 → ... → 1 这条线，深度为 n。所以空间复杂度是 O(n)。这里经常有人答成 O(2^n)，千万别踩坑。

从工程角度看，斐波那契朴素递归是典型的“能用但绝对不能用于生产”的代码。n=50 时递归调用次数已经超过 10 亿次，肉眼可见地卡死。第 5 节的记忆化就是它的终极解药。

4.3 案例三：归并排序——分治的黄金模板

归并排序是分治递归的样板，它同时体现了“递推式、主定理、递归树”的分析思路。

function mergeSort(arr) { if (arr.length <= 1) return arr; const mid = Math.floor(arr.length / 2); const left = mergeSort(arr.slice(0, mid)); const right = mergeSort(arr.slice(mid)); return merge(left, right); }

递推式为：

T(n) = 2T(n/2) + O(n)

这里 a=2、b=2、f(n)=O(n)。根据主定理情形 2，n^(log₂2) = n 与 f(n) 同阶，因此：

T(n) = Θ(n log n)

时间复杂度的结论很干净。空间复杂度要分两部分看。递归栈部分：递归树深度 log₂n，栈帧空间 O(log n)。但我们写归并时通常还会开辟一个临时数组来merge，如果每次递归都新建数组，那所有层的临时数组加起来会是 O(n log n)；如果整体只用一个缓冲区，则是 O(n)。所以在实际分析时，我一般给出的结论是“空间复杂度 O(n)”，并且额外说明其中的栈开销只有 O(log n)。

这个细节在面试里也很常见：问归并排序的空间复杂度到底是不是 O(n)？“是”要看怎么算辅助数组。我自己在写作和教学时，习惯把“递归栈”和“额外辅助空间”分开报，面试官会觉得你对系统栈有概念，而不是背答案。

4.4 案例四：二分查找——主定理的直观应用

二分查找递归版：

function binarySearch(nums, target, left, right) { if (left > right) return -1; const mid = Math.floor((left + right) / 2); if (nums[mid] === target) return mid; if (target < nums[mid]) { return binarySearch(nums, target, left, mid - 1); } return binarySearch(nums, target, mid + 1, right); }

递推式：

T(n) = T(n/2) + O(1)

a=1、b=2，n^(log₂1) = 1，f(n)=O(1)，主定理情形 2，结论：

T(n) = Θ(log n)

空间方面，递归栈深度是 log₂n，每层常数空间，所以空间复杂度 O(log n)。注意这里和循环版二分查找空间 O(1) 的区别。循环版不需要栈帧，递归版则必须付出递归深度对应的空间。因此问“递归版二分查找空间复杂度”时，答案是 O(log n)，不是 O(1)。这可以说是高频考点，我至少见过三次面试题直接栽在这上面。

四个案例放在一起对比，可以得出一个很明显的规律：

这个表建议直接存下来。面试考递归复杂度时，90%的题最终都能归到这几类里。

5. 从“能跑”到“能扛”：递归优化的三条路

分析复杂度不是最终目的，最终目的是把复杂度降下来。递归的优化最常用的三条路是记忆化、尾递归改写、以及迭代替代。三条路各有适用场景，下面逐个说清楚。

5.1 记忆化递归：用空间换时间

斐波那契的指数爆炸，本质上是因为同一个子问题被反复求解。比如 fib(5) 会分别从 fib(6) 和 fib(7) 两条路径里被调用，而 fib(5) 下面的 fib(4) 又被重复算了无数次。解决办法是加一个缓存，把已经算过的结果存下来，下次直接取。

用 JavaScript 写一个带缓存的记忆化递归：

function fibMemo(n, memo = {}) { if (n <= 2) return 1; if (memo[n] !== undefined) return memo[n]; memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo); return memo[n]; }

加了缓存之后，每个规模 n 最多只被计算一次。子问题的数量从指数级降为 O(n)，所以时间从 O(2^n) 降到 O(n)，空间是 O(n)。记忆化的本质是“用空间换时间”，这也是动态规划自顶向下写法的雏形。实际开发里，如果递归里有大量重复子问题（重叠子问题），第一反应就应该是记忆化，而不是急着改写循环。

一个细节：记忆化键的选择。如果递归参数不只一个，空间维度就变高，缓存不能用一维数组，得用 Map 或者二维矩阵。以双参数递归为例，缓存命中率直接决定优化效果，别在键的设计上偷懒。

5.2 尾递归改写：参数里藏结果

尾递归的核心思想是：状态不通过返回值在“归”的过程中传递，而是在“递”的过程中通过参数传递。前面说过阶乘的尾递归写法，这里再举一个树的深度计算例子。

普通递归：

function treeDepth(root) { if (root === null) return 0; return 1 + Math.max(treeDepth(root.left), treeDepth(root.right)); }

这个无法简单改写成单一路径的尾递归，因为有两个子问题，尾递归只对单个递推路径的最简单场景有效。遇到这种多路递归，尾递归不是最优解，记忆化或者显式栈才是出路。

所以我建议在面试或工程里区分看待尾递归：尾递归是优化“线性递归空间”的巧妙方案，不是万能药。在支持尾调用优化的语言里，它很香；在不支持的语言里，它只是换了一种写法，复杂度没变。写代码前先确认语言环境是硬道理。

5.3 工程判断：什么时候该保留递归，什么时候该改成迭代

从工程角度讲，用不用递归不能只看复杂度，还要看可读性、栈深度、语言限制。我一般按下面这几条来判断：

1. 递归深度不大（比如 log n 级别），代码直观，保留。典型场景是树结构的遍历、二分查找、归并排序。
2. 递归深度可能到几千上万级，哪怕时间复杂度合格，也可能栈溢出。典型场景是深度很大的链表操作、DFS 遍历超大图，此时强烈建议改成显式栈或迭代。
3. 递归版本存在明显重叠子问题，先做记忆化，不行再改迭代。
4. 团队成员对递归普遍不熟，且没有强性能要求，循环版本可能更利于维护。

举一个工程里的真实感受：我在处理一个树形层级结构的 JSON 时，递归代码非常漂亮，深度也很浅，完全没问题；后来把数据源换成了一个深层嵌套的测试数据，递归直接爆栈，整组人的第一反应是“怎么还好好的就崩了”。这件事给我的教训是，递归版本上线前要评估实际的最大递归深度，不能只看算法本身——这是工程经验和纯算法分析最大的分水岭。

6. 实战排查实录：六个高频翻车问题与纠偏

这一节是“排雷”环节。我把这些年见过的递归复杂度高频错误集中列出来，配上诊断思路和纠正方案，方便你写代码、面试前自查。

6.1 主定理用错 a 和 b

常见错误：看到 T(n) = 2T(n/2) + n² 直接套主定理情形 2，理由是“n² 和 n 都是多项式嘛”。这是对主定理使用条件理解不透彻。

正确做法是：a=2、b=2，n^(log₂2) = n，f(n) = n²。因为 n² 比 n 大了 n 倍，落进情形 3 的条件范围，结论是 T(n) = Θ(n²)。用递归树验证也很直观：第一层 n²，第二层 2×(n/2)² = n²/2，第三层 4×(n/4)² = n²/4，逐层等比衰减，总和收敛于 2n²，所以 Θ(n²)。结论一致。

排查技巧：遇到主定理之前，先算 n^(log_b a) 这个基准量，再和 f(n) 比。比大小的标准要明确到“是不是相差一个多项式因子（比如 n^ε）”，而不仅仅是“谁大谁小”。

6.2 斐波那契空间复杂度答错

这是我看过最多次的错误：因为递归树有 2^n 个节点，所以连空间复杂度也答 O(2^n)。纠正方法是画出调用过程的时间线。

递归的执行方式不是“同时计算所有节点”，而是“深度优先”推进。从 fib(n) 出发，会一路递归到 fib(1)，然后逐步返回，再进入另一分支。任何时刻调用栈里的帧数是当前路径长度，最多 n。所以空间 O(n)。时间 O(2^n)、空间 O(n)，这一组数据要记牢。

6.3 二分查找的递推式不会列

有时候面试者知道二分查找时间复杂度是 O(log n)，但让他写递推式却写成了 T(n) = 2T(n/2) + O(1)。错就错在把二分查找当成了“一个数组拆成两半分别查”。

实际上二分查找每次只进入 left 半区或 right 半区，不是两个都去。所以递推式是 T(n) = T(n/2) + O(1)，a=1 而不是 2。如果用 a=2 去套主定理，结果是 Θ(n)，那就闹大笑话了。这个小坑提醒我们，写递推式前要仔细看代码分支：分支是二选一，还是两个都走。

6.4 递归反转链表的空间复杂度容易被漏算

比如反转链表的递归写法：

function reverseList(head) { if (head === null || head.next === null) return head; const newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; }

时间复杂度 O(n) 毫无疑问，每个节点处理一次。空间复杂度不只是局部变量几个，因为链表有 n 个节点，递归调用会一直压到链尾，最深 n 层，栈帧 O(n)，所以空间是 O(n)。这个案例特别适合提醒“栈深度可能等于输入规模”这一类问题。如果要求 O(1) 空间，就得改成迭代。

6.5 图 DFS 的栈空间按“深度”而非“宽度”估算

图上的递归 DFS，有人会把所有访问过的节点都算进空间，但这个跟递归空间不是一回事。递归 DFS 的空间主要是系统栈的深度，而深度最坏情况等于图的连通路径最大长度。如果是一条链状图，深度就是 O(n)；如果是星型图，深度只有 O(1) 层。空间复杂度要按最大栈深度算，跟整个图有多少个节点没有必然关系。至于 visited 数组或哈希表，那是“辅助数据结构”，要单独列出。在面试里最好这样分层汇报：栈空间 O(d)（最大深度），辅助空间 O(V)（访问标记），总空间 O(V+d)。这样拆开讲，表现力比直接说一句“O(V)”强得多。

6.6 “递归一定慢”的认知误区

有人一听到递归，就下意识说“性能不行”。实际上递归只是一种结构，不是性能的代名词。分治递归里如果一个递归函数内部工作能被编译器优化、或者子问题复杂度和循环完全一致，那递归未必比循环慢。真正要警惕的是：

• 无谓的重复计算（重叠子问题）；
• 过深的栈深度导致栈溢出；
• 创建了大量中间对象（比如每次递归创建一个新数组）。

这几个才是性能杀手，而不是“递归”这个形式本身。我见过不少用循环硬写树遍历写出一堆 bug 的代码，回头用递归版本几行就解决了，性能一样是 O(n)。所以判断标准始终是复杂度，不是“贴不贴递归”的标签。

以上这六类问题是递归复杂度分析里最典型的过山车式翻车点，面试前过一遍，基本不会在核心环节掉链子。我自己的体会是：多做几个案例的递归树展开，比背十遍主定理结论都管用。递归复杂度分析的难点从来不在于数学，而在于“敢不敢把每一层实际发生的事情画出来”。只要画得出树，量的估算就顺理成章。你想真正掌握它，最好的办法就是拿几个经典递归案例，按这篇文章的方法从头到尾自己算一遍，算完你就能体会到什么叫“心中有树，眼里有复杂度”。