递归运行时 - 空间复杂度（《破解编码面试》第 44 页）

Question

上页。《破解编码面试》第 44 章有以下算法：

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

书上说它的时间复杂度为 O(2^n) ，空间复杂度为 O(n) 。我得到了时间复杂度部分，因为创建了 O(2^n) 个节点。我不明白为什么空间复杂度不是这样。书上说因为这是因为在任何给定时间只存在 O(n) 个节点。

怎么可能？当我们处于 f(1) 的底层时，调用堆栈不会包含所有 2^n 次调用吗？我缺少什么？

如果我可以提供更多详细信息，请告诉我。

谢谢，

Answer 1

不会。第二次调用要f(n-1)等到第一个调用返回后才会发生，因此它们不会同时占用堆栈空间。当第一个返回时，其堆栈空间被释放，并可以重新用于第二次调用。

这同样适用于递归的每个级别。使用的内存与调用树的最大深度成正比，而不是与节点总数成正比。