评估递归算法复杂度需分时间与空间：时间看递归树总工作量，空间看调用栈最大深度；优化空间关键在控制栈帧高度与单帧开销，而非减少调用次数。

评估递归算法的复杂度，核心是分开看时间与空间：时间取决于整棵递归树的总工作量，空间取决于调用栈的最大深度。优化空间复杂度的关键不是减少调用次数，而是控制栈帧堆积的高度和每个栈帧的内存开销。

时间复杂度：算清整棵树干了多少活

不能只数“调用了几次函数”，而要看所有递归分支加起来做了多少操作：

• 画小规模递归树（比如 n=4 或 n=8），观察每层节点数和每个节点做的工作量（是 O(1) 比较？还是 O(n) 遍历？）
• 总时间 ≈ 树中节点总数 × 单节点平均工作量
• 斐波那契朴素递归：树近似满二叉，节点数约 2ⁿ，每节点 O(1)，所以 T(n) = O(2ⁿ)
• 二分查找递归：每次只走一个分支，树高 log₂n，每层 O(1)，所以 T(n) = O(log n)
• 归并排序递归：共 O(log n) 层，每层所有子问题合计做 O(n) 工作，所以 T(n) = O(n log n)

空间复杂度：盯住调用栈最深那一摞

JavaScript 是单线程 + 调用栈执行，空间开销主要来自栈帧数量，不是所有分支同时存在：

• 最大递归深度 = 从根到最深叶子的边数
• 每个栈帧含参数、局部变量、返回地址；若每次递归新建数组或对象，要额外计入这部分空间
• 斐波那契朴素递归：最坏路径是 n→n−1→…→0，深度为 n，空间为 O(n)
• 平衡二叉树 DFS：深度约 log₂n，空间为 O(log n)
• 链状树 DFS：深度达 n，空间退化为 O(n)

降低空间复杂度的实用方法

目标是压低栈深度或减小单帧体积，而不是消灭递归：

• 优先用迭代重写：比如二叉树中序遍历、斐波那契、阶乘，都能转为 while 循环 + 显式栈/变量，空间直接降到 O(1)
• 避免在递归中复制数据：传索引代替切片数组，用原数组+左右边界参数，防止每次递归都生成新子数组
• 尾递归写法（虽不被 JS 引擎优化，但结构更清晰）：确保递归调用是函数最后动作，不依赖返回值做后续计算，便于人工转为迭代
• 限制递归深度或改用 BFS：对特别深的树，可改用队列实现层序遍历，把栈空间换为堆空间，避免爆栈

别踩这些常见坑

容易误判的地方，往往就藏在直觉里：

• 认为“没 new 对象”就一定是 O(1) 空间——忽略了调用栈本身占内存
• 把分支数当时间基数（如看到两个递归调用就以为是 O(2ⁿ)）——实际要看树是否真满、每层是否真膨胀
• 以为记忆化能降空间——它用哈希表换时间，空间常升为 O(n)，栈深度不变
• 期待 JS 自动做尾递归优化——目前主流引擎未启用，尾递归仍占 O(n) 栈空间