递归算法时间空间复杂度分析

递归算法的复杂度分析常被误解为简单统计调用次数，实则关键在于构建并解读递归树：时间复杂度由整棵树所有节点的总工作量决定——无论是指数级爆炸的斐波那契、对数级收敛的二分查找，还是线性对数的归并排序；而空间复杂度则只取决于调用栈的最大深度，即从根到最深叶的路径长度，与分支数量无关。本文直击常见误区，揭示“为什么斐波那契空间是O(n)而非O(2ⁿ)”、“尾递归在JS中为何几乎不省空间”等本质问题，并提供四步实战估算法，帮你真正看懂递归背后的计算代价。

递归算法的时间与空间复杂度不能只看函数调用了几次，关键得看「递归树的总节点数」和「最大递归深度」。

时间复杂度：取决于递归树的总工作量

每次递归调用本身可能做常数工作（如加减、比较），也可能做线性工作（如遍历数组）。真正决定时间复杂度的是整棵递归树中所有节点执行的操作总和。

• 例如斐波那契朴素递归 f(n) = f(n-1) + f(n-2)：递归树近似满二叉树，节点总数约 O(2ⁿ)，所以时间复杂度是 O(2ⁿ)
• 再如二分查找递归实现：每次只走一个分支，树高 log₂n，每层仅 O(1) 工作，总时间就是 O(log n)
• 又如归并排序递归版：递归树有 O(n) 个叶节点，每层总操作量为 O(n)，共 O(log n) 层 → 总时间 O(n log n)

空间复杂度：由调用栈深度主导

JavaScript 是单线程、基于调用栈执行的环境。每次递归调用都会压入一个栈帧，保存局部变量、参数和返回地址。空间开销主要取决于「最大同时存在的栈帧数量」，即递归的最大深度。

• 斐波那契朴素递归最大深度是 n → 空间复杂度 O(n)（注意：不是 O(2ⁿ)，栈不会并行存所有分支）
• 二叉树深度优先遍历（最坏链状树）：最大深度 O(n) → 空间 O(n)
• 平衡二叉树 DFS：最大深度 O(log n) → 空间 O(log n)
• 尾递归在 JS 中基本不被优化（ES2015 规范虽定义但主流引擎未启用），所以不能默认按 O(1) 栈空间估算

常见误区提醒

容易把「分支数」直接当成时间复杂度基数，或误认为每次递归都占用独立的全部内存。实际上：

• 时间看的是「所有递归调用执行的总操作数」，不是调用次数本身
• 空间看的是「调用栈纵向堆积的最大层数」，不是横向分支数量
• 若递归中创建新数组、对象等，需额外计入这些数据结构的空间（如每次复制子数组，就可能引入 O(n²) 额外空间）
• 避免在递归内做重复计算（如斐波那契），可用记忆化将时间从 O(2ⁿ) 降至 O(n)，空间变为 O(n)（缓存 + 栈）

快速估算步骤

分析一个递归函数时，可按这四步走：

• 写出递推关系式（如 T(n) = 2T(n/2) + O(n)）
• 画出小规模的递归树（n=4 或 n=8），观察每层节点数和每节点工作量
• 算总节点数 × 平均单节点工作量 → 得时间复杂度
• 数从根到最深叶的边数 → 得栈深度 → 得空间复杂度

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《递归算法时间空间复杂度分析》文章吧，也可关注golang学习网公众号了解相关技术文章。