int f(int n) { if (n <= 1) { return 1; } return f(n - 1) + f(n - 1); }
我知道时间很复杂，O(2^n)而且我理解为什么。
O(2^n)
但是我不明白为什么空间复杂O(n)。有人告诉我，这是因为在任何给定时间都只有n节点，但这对我来说没有意义。
O(n)
n
因为第二个要f(n-1)等到第一个完成后才能运行（反之亦然- 两种方法都相同）。第一次调用将递归n时间，然后所有这些都将返回，因此将总共推送n堆栈帧。然后，第二个呼叫将执行相同的操作。
f(n-1)
因此，它n在递归中的作用永远不会超过层次，这是造成空间复杂性的唯一因素。
