这是《破解编码访谈》（第5版）中斐波那契数列的递归实现
int fibonacci(int i) {
if(i == 0) return 0;
if(i == 1) return 1;
return fibonacci(i-1) + fibonaci(i-2);
}
在观看了有关此算法的时间复杂度的视频（斐波那契时间复杂度）之后，我现在明白了为什么该算法在O（2n）中运行。然而，我正在努力分析空间复杂性。
我在网上看了一下，对此有一个问题。
在这个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);
打印出来的“堆栈”的最高值是多少。你会看到它是“6”。尝试“i”的其他值，您将看到打印的“堆栈”值永远不会高于传入的原始“i”值。
由于Fib（i-1）在Fib（i-2）之前被完全评估，因此永远不会超过递归水平。i
因此，O（N）。
递归实现的近似时间复杂度为2平方n（2^n），这意味着该算法必须经过大约64个计算步骤才能得到第6个斐波那契数列。这是巨大的，不是最佳的，它将需要大约程序1073741824计算步骤才能得到斐波那契数列30，这是一个小数字，这是不可接受的。实际上，迭代方法肯定更好且经过优化。
在了解了此实现的时间复杂性之后，人们可能会认为它的空间复杂性可能是相同的，但事实并非如此。此实现的空间复杂度等于 O（n），并且永远不会超过它。所以，让我们揭开“为什么”的神秘面纱？
这是因为递归执行的函数调用乍一看似乎是并发执行的，但实际上，它们是按顺序执行的。
顺序执行保证堆栈大小永远不会超过上图所示的调用树的深度。程序首先执行所有最左侧的调用，然后转向右侧，当 F0 或 F1 调用返回时，其相应的堆栈帧会弹出。
在下图中，每个矩形表示一个函数调用，箭头表示程序到达递归末尾的路径：
我们在这里可以注意到的是，当程序到达调用F4F3F2F1并返回1时，它会返回到其父调用F4F3F2以执行正确的递归子调用F4F3F2F0，当F4F3F2F0和F4F3F2F1调用返回时，程序返回到F4F3。因此，堆栈永远不会超过最长路径 F4F3F2F1 的大小。
该程序将遵循相同的执行模式，从父项到子项，并在执行左键和右键调用后返回到父项，直到它到达所有F4的最后一个根父项，从而得出斐波那契的计算和，即3。
