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

这是《破解编码面试》（第五版）中斐波那契数列的递归实现

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

After watching the video on the time complexity of this algorithm, Fibonacci Time Complexity https://www.youtube.com/watch?v=ncpTxqK35PI, I now understand why this algorithm runs in O(2ⁿ). However, I am struggling with analyzing the space complexity.

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

在这个 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) 吗？

这是一个提示。使用 print 语句修改代码，如下例所示：

int fibonacci(int i, int stack) {
    printf("Fib: %d, %d\n", i, stack);
    if (i == 0) return 0;
    if (i == 1) return 1;
    return fibonacci(i - 1, stack + 1) + fibonacci(i - 2, stack + 1);
}

现在在 main 中执行这一行：

Fibonacci(6,1);

打印出来的“stack”的最高值是多少。你会看到它是“6”。尝试“i”的其他值，您会发现打印的“stack”值永远不会高于传入的原始“i”值。

由于 Fib(i-1) 在 Fib(i-2) 之前完成评估，因此永远不会超过i递归级别。

因此，O(N)。