CTCI书中的递归算法的空间复杂度[重复]

Question

我正在阅读CTCI书，无法理解其中的一个例子。他们开始于：

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

并说明这是O（n）时间和O（n）空间，因为每个调用都添加到了调用堆栈中并占用了实际内存。下一个示例是：
int f(int n) {
  if (n <= 0) {
    return 1;
  }
  return f(n - 1) + f(n-1);
}

并指出时间复杂度为O（2 ^ n），空间为O（n）。尽管我理解为什么时间是O（2 ^ n），但我不确定为什么空间是O（n）？他们的解释是“在任何给定时间仅存在O（n）个节点”。为什么我们不像第一个示例那样计算每个调用堆栈占用的空间？

P.S。阅读了类似的问题之后，一旦我们开始向后（或向上）移动递归，我是否应该假定堆栈框架的空间已被回收？

Answer 1

与时间复杂度不同，时间复杂度只是运行程序所需的总时间，而空间复杂度则描述了执行程序所需的空间。因此，在程序的执行树中有2

n个节点并不重要。调用堆栈会自动折叠并释放所用的额外内存。重要的是调用树的最大深度，对于此程序为O（n）。但是，应注意的是，递归是一种特殊情况，在堆栈折叠时自然释放所有已用的内存。如果在运行时显式分配了内存，则也应显式释放它。

^{关于第一个示例，调用树只是深度为n的列表，导致O（n）的复杂度类似。}