递归算法的时间复杂度取决于递归树的节点总数，空间复杂度由最大递归深度决定；线性递归为O(n)时间与空间，二叉递归如fib(n)时间O(2ⁿ)、空间O(n)，分治递归如归并排序为O(n log n)时间、O(log n)空间。
递归算法的时间复杂度和空间复杂度不能一概而论，必须结合具体函数的调用结构、子问题划分方式以及是否重复计算来分析。核心在于：时间复杂度看“总递归调用次数”，空间复杂度看“最大递归调用深度”（即调用栈的最大长度）。
时间复杂度：取决于递归树的节点总数
递归过程通常可建模为一棵递归树。每个节点代表一次函数调用，其子节点对应该次调用产生的下一层递归调用。
- 线性递归（如阶乘
factorial(n)）：每次只产生一个子调用，递归深度为n，共n次调用 → 时间复杂度 O(n) - 二叉递归（如朴素斐波那契
fib(n)）：每次调用分裂为两个子调用，递归树近似满二叉树，节点数约2ⁿ→ 时间复杂度 O(2ⁿ) - 分治递归（如归并排序的递归版）：每次将问题拆成两半，树高
log₂n，每层总工作量为O(n)→ 时间复杂度 O(n log n)
空间复杂度：由调用栈深度主导
JavaScript 引擎为每次函数调用分配栈帧（保存参数、局部变量、返回地址等）。递归深度即栈帧最多同时存在的数量。
- 线性递归（如
factorial(n)）：调用链为n → n−1 → … → 1，最大深度n→ 空间复杂度 O(n) - 尾递归（如带累加器的
factorial(n, acc = 1)）：理论上可被优化为迭代，但当前主流 JavaScript 引擎（Chrome/V8、Firefox）默认不启用尾调用优化（TCO），所以仍为 O(n) - 树形递归（如
fib(n)）：最大深度仍是n（最左/最右路径），不是节点总数 → 空间复杂度仍是 O(n)
常见误区与优化方向
容易误把“重复计算”当成空间开销，其实它影响的是时间而非空间；也容易忽略引擎实际行为（如 TCO 不可用）。
立即学习“Java免费学习笔记（深入）”；
-
避免朴素指数级时间：对重叠子问题（如斐波那契、爬楼梯），改用记忆化（
memo对象或数组缓存结果）可降至 O(n) 时间与空间 - 显式用栈模拟递归：可将递归转为迭代，精确控制内存使用，规避栈溢出风险（尤其处理深层嵌套数据时）
-
注意调用栈限制：V8 默认栈深约 10⁴–10⁵ 层，
RangeError: Maximum call stack size exceeded即由此触发
简单验证方法
可通过计数器粗略估算：
- 加全局计数器统计调用次数 → 逼近时间复杂度量级
- 传入深度参数
depth并更新最大值 → 可得实际最大调用深度，验证空间复杂度 - 用
console.trace()在深层调用中触发，观察堆栈帧数量（仅调试用）
