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

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

在观看了有关该算法的时间复杂度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）吗？