《程序员面试金典》44页递归算法空间复杂度O(n)疑问

int f(int n) {
    if (n <= 1) {
        return 1;
    }
    return f(n - 1) + f(n - 1);
}

你理解的偏差核心在于把「总调用次数」和「同一时刻存活的调用栈帧」概念搞混了，另外递归是串行执行的，不存在所有调用同时存在于栈中的情况。

我们以n=3为例拆解完整执行过程和栈的变化：

1. 调用f(3)，栈帧入栈，当前栈：[f(3)]，深度1
2. 计算f(3)的第一个加数f(2)，f(2)入栈，当前栈：[f(3), f(2)]，深度2
3. 计算f(2)的第一个加数f(1)，f(1)入栈，当前栈：[f(3), f(2), f(1)]，深度3
4. f(1)命中终止条件返回1，f(1)栈帧弹出释放，当前栈回到[f(3), f(2)]，深度2
5. 计算f(2)的第二个加数f(1)，f(1)入栈，当前栈：[f(3), f(2), f(1)]，深度3
6. f(1)返回1，f(1)栈帧弹出，当前栈回到[f(3), f(2)]，深度2
7. f(2)计算完成（1+1=2），f(2)栈帧弹出释放，当前栈回到[f(3)]，深度1
8. 计算f(3)的第二个加数f(2)，f(2)入栈，后续执行逻辑和步骤3-7完全一致，全程栈的最大深度始终是3
9. 所有计算完成后f(3)弹出，栈为空

从上面的过程可以明确几个结论：

• 总调用次数符合2^{n的规律，所以时间复杂度为O(2}n)，和你的理解一致
• 栈的最大深度等于n：最多就是从f(n)一路递归到f(1)的n层，每一个子调用执行完成后栈帧就会立即释放，不会一直保留，同一时刻内存里最多只有n个栈帧存在
• 空间复杂度统计的是程序运行过程中的峰值内存占用，不是累计占用的内存总量，所以该算法的空间复杂度是O(n)

你之前的疏漏就是默认所有2^n个调用的栈帧会同时存在，但实际上同一个父节点下的两个f(n-1)调用是一先一后执行的，后一个开始执行的时候，前一个的栈帧已经完全释放了，不会同时留在内存里。

内容的提问来源于stack exchange，提问作者Python Developer