递归运行时 - Space 复杂性（Cracking the Coding Interview 第 44 页）
Recursive Runtime - Space Complexity (pg.44 of Cracking the Coding Interview)
上页。 44 of Cracking the Coding Interview，算法如下：
int f(int n) {
if (n <= 1) {
return 1;
}
return f(n - 1) + f(n - 1);
}
书上说这有O(2^n)的时间复杂度和O(n)的space-复杂度。我得到了时间复杂度部分，因为创建了 O(2^n) 个节点。我不明白为什么 space-复杂性不是那样。书上说因为这是因为在任何给定时间只存在 O(n) 个节点。
怎么可能？当我们处于 f(1) 的底层时，调用堆栈不会包含所有 2^n 次调用吗？我错过了什么？
如果我可以提供更多详细信息，请告诉我。
谢谢，
没有。第二次调用 f(n-1) 直到第一次调用 returns 之后才会发生，因此它们不会同时占用堆栈 space。当第一个 returns 时，它的堆栈 space 被释放并且可以重新用于第二个调用。
这同样适用于递归的每一层。使用的内存与调用树的最大深度成正比，而不是节点总数。
上页。 44 of Cracking the Coding Interview，算法如下：
int f(int n) {
if (n <= 1) {
return 1;
}
return f(n - 1) + f(n - 1);
}
书上说这有O(2^n)的时间复杂度和O(n)的space-复杂度。我得到了时间复杂度部分，因为创建了 O(2^n) 个节点。我不明白为什么 space-复杂性不是那样。书上说因为这是因为在任何给定时间只存在 O(n) 个节点。
怎么可能？当我们处于 f(1) 的底层时，调用堆栈不会包含所有 2^n 次调用吗？我错过了什么？
如果我可以提供更多详细信息，请告诉我。
谢谢，
没有。第二次调用 f(n-1) 直到第一次调用 returns 之后才会发生，因此它们不会同时占用堆栈 space。当第一个 returns 时，它的堆栈 space 被释放并且可以重新用于第二个调用。
这同样适用于递归的每一层。使用的内存与调用树的最大深度成正比，而不是节点总数。