递归斐波那契算法的空间复杂度是多少？

这是从《破解编码面试》（第5版）开始的Fibonacci序列的递归实现。

int fibonacci(int i) {
       if(i == 0) return 0;
       if(i == 1) return 1;
       return fibonacci(i-1) + fibonaci(i-2);
}

在观看了有关该时间复杂度" title="算法的时间复杂度">算法的时间复杂度Fibonacci时间复杂度的视频后，我现在了解了为什么该算法以O（2

n ）运行。但是，我正在努力分析空间的复杂性。

我在网上看了一下，对此有疑问。

在这个Quora线程中，作者声明“在您的情况下，您有n个堆栈帧f（n），f（n-1），f（n-2），…，f（1）和O（1

）”。您不会有2n个堆栈帧吗？对f（n-2）说一句话，实际呼叫f（n-2）会是一帧，但f（n-1）不会也有呼叫f（n-2）吗？

如果其他人仍然感到困惑，请务必观看此YouTube视频，其中讨论了生成斐波那契数列的空间复杂性。斐波那契空间复杂性

演示者非常清楚地说明了为什么空间复杂度为O（n），递归树的高度为n。