算法分析这件事我最常听到的一句话是“递归的代码我能看懂一问时间复杂度就答不上来。”尤其是刷题遇到那种递归解法题目能 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 统一递推式 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。上例中 a2、b2所以画两个子节点每个规模 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、b1就能套用。它的核心思想是拿 f(n) 和 n^(log_b a) 比大小那个“谁更大复杂度就由谁决定”。更精确地说情形条件f(n) 的量级结论 T(n)1f(n) n^(log_b a)且差一个多项式因子Θ(n^(log_b a))2f(n) ≈ n^(log_b a)可能乘一个 log 的幂Θ(n^(log_b a) log n)3f(n) n^(log_b a)且满足正则条件Θ(f(n))这么说可能还是抽象我换成人话如果 n^(log_b a) 明显比 f(n) 大说明递归本身的开销占主导。如果两者差不多大说明递归开销和每层额外工作“势均力敌”结果要在外面多乘一个 log n。如果 f(n) 明显比 n^(log_b a) 大说明每层的额外工作才是主角复杂度由 f(n) 决定。举两个高频例子。归并排序T(n) 2T(n/2) O(n)。这里 a2、b2所以 n^(log₂2) n。而 f(n) n两者同阶对应情形 2。结论T(n) Θ(n log n)。二分查找T(n) T(n/2) O(1)。这里 a1、b2n^(log₂1) 1f(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)。要证明它需要证明存在常数 c0 和 n₀0使得对所有 n≥n₀ 有 T(n) ≤ c·n·log₂n。归纳证明的步骤是这样假设 T(k) ≤ c·k·log₂k 对于所有 kn 成立然后代入原递推式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。通常我取 c2再补上边界条件检查就能完成证明。这个证明过程中有一个细节值得记住别把 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)千万别踩坑。从工程角度看斐波那契朴素递归是典型的“能用但绝对不能用于生产”的代码。n50 时递归调用次数已经超过 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)这里 a2、b2、f(n)O(n)。根据主定理情形 2n^(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)a1、b2n^(log₂1) 1f(n)O(1)主定理情形 2结论T(n) Θ(log n)空间方面递归栈深度是 log₂n每层常数空间所以空间复杂度 O(log n)。注意这里和循环版二分查找空间 O(1) 的区别。循环版不需要栈帧递归版则必须付出递归深度对应的空间。因此问“递归版二分查找空间复杂度”时答案是 O(log n)不是 O(1)。这可以说是高频考点我至少见过三次面试题直接栽在这上面。四个案例放在一起对比可以得出一个很明显的规律案例递推式时间空间关键点阶乘T(n) T(n-1) O(1)O(n)O(n)线性递归栈深度等于输入规模斐波那契朴素T(n) T(n-1) T(n-2) O(1)O(2^n)O(n)树形递归时间爆炸空间还在归并排序T(n) 2T(n/2) O(n)O(n log n)O(n)分治辅助数组是主导空间二分查找T(n) T(n/2) O(1)O(log n)O(log n)单路分治栈深度是 log这个表建议直接存下来。面试考递归复杂度时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 工程判断什么时候该保留递归什么时候该改成迭代从工程角度讲用不用递归不能只看复杂度还要看可读性、栈深度、语言限制。我一般按下面这几条来判断递归深度不大比如 log n 级别代码直观保留。典型场景是树结构的遍历、二分查找、归并排序。递归深度可能到几千上万级哪怕时间复杂度合格也可能栈溢出。典型场景是深度很大的链表操作、DFS 遍历超大图此时强烈建议改成显式栈或迭代。递归版本存在明显重叠子问题先做记忆化不行再改迭代。团队成员对递归普遍不熟且没有强性能要求循环版本可能更利于维护。举一个工程里的真实感受我在处理一个树形层级结构的 JSON 时递归代码非常漂亮深度也很浅完全没问题后来把数据源换成了一个深层嵌套的测试数据递归直接爆栈整组人的第一反应是“怎么还好好的就崩了”。这件事给我的教训是递归版本上线前要评估实际的最大递归深度不能只看算法本身——这是工程经验和纯算法分析最大的分水岭。6. 实战排查实录六个高频翻车问题与纠偏这一节是“排雷”环节。我把这些年见过的递归复杂度高频错误集中列出来配上诊断思路和纠正方案方便你写代码、面试前自查。6.1 主定理用错 a 和 b常见错误看到 T(n) 2T(n/2) n² 直接套主定理情形 2理由是“n² 和 n 都是多项式嘛”。这是对主定理使用条件理解不透彻。正确做法是a2、b2n^(log₂2) nf(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)a1 而不是 2。如果用 a2 去套主定理结果是 Θ(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(Vd)。这样拆开讲表现力比直接说一句“O(V)”强得多。6.6 “递归一定慢”的认知误区有人一听到递归就下意识说“性能不行”。实际上递归只是一种结构不是性能的代名词。分治递归里如果一个递归函数内部工作能被编译器优化、或者子问题复杂度和循环完全一致那递归未必比循环慢。真正要警惕的是无谓的重复计算重叠子问题过深的栈深度导致栈溢出创建了大量中间对象比如每次递归创建一个新数组。这几个才是性能杀手而不是“递归”这个形式本身。我见过不少用循环硬写树遍历写出一堆 bug 的代码回头用递归版本几行就解决了性能一样是 O(n)。所以判断标准始终是复杂度不是“贴不贴递归”的标签。以上这六类问题是递归复杂度分析里最典型的过山车式翻车点面试前过一遍基本不会在核心环节掉链子。我自己的体会是多做几个案例的递归树展开比背十遍主定理结论都管用。递归复杂度分析的难点从来不在于数学而在于“敢不敢把每一层实际发生的事情画出来”。只要画得出树量的估算就顺理成章。你想真正掌握它最好的办法就是拿几个经典递归案例按这篇文章的方法从头到尾自己算一遍算完你就能体会到什么叫“心中有树眼里有复杂度”。
