递归算法的时间复杂度取决于递归树总节点数与各节点工作量之积，空间复杂度由最大递归深度（即调用栈最大高度）决定；斐波那契朴素递归为O(2ⁿ)时间、O(n)空间，二分查找为O(log n)时间与空间，归并排序为O(n log n)时间、O(log n)空间。
递归算法的时间与空间复杂度不能只看函数调用了几次，关键得看「递归树的总节点数」和「最大递归深度」。
时间复杂度：取决于递归树的总工作量
每次递归调用本身可能做常数工作（如加减、比较），也可能做线性工作（如遍历数组）。真正决定时间复杂度的是整棵递归树中所有节点执行的操作总和。
- 例如斐波那契朴素递归
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) 栈空间估算
常见误区提醒
容易把「分支数」直接当成时间复杂度基数，或误认为每次递归都占用独立的全部内存。实际上：
立即学习“Java免费学习笔记（深入）”；
- 时间看的是「所有递归调用执行的总操作数」，不是调用次数本身
- 空间看的是「调用栈纵向堆积的最大层数」，不是横向分支数量
- 若递归中创建新数组、对象等，需额外计入这些数据结构的空间（如每次复制子数组，就可能引入 O(n²) 额外空间）
- 避免在递归内做重复计算（如斐波那契），可用记忆化将时间从 O(2ⁿ) 降至 O(n)，空间变为 O(n)（缓存 + 栈）
快速估算步骤
分析一个递归函数时，可按这四步走：
- 写出递推关系式（如 T(n) = 2T(n/2) + O(n)）
- 画出小规模的递归树（n=4 或 n=8），观察每层节点数和每节点工作量
- 算总节点数 × 平均单节点工作量 → 得时间复杂度
- 数从根到最深叶的边数 → 得栈深度 → 得空间复杂度
