java 递归斐波那契算法的空间复杂度是多少？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/28756045/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the space complexity of a recursive fibonacci algorithm?
提问by committedandroider
This is the recursive implementation of the Fibonacci sequence from Cracking the Coding Interview (5th Edition)
这是 Cracking the Coding Interview（第 5 版）中斐波那契数列的递归实现
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, I now understand why this algorithm runs in O(2n). However I am struggling with analyzing the space complexity.
在观看了有关该算法时间复杂度 Fibonacci Time Complexity的视频后，我现在明白了为什么该算法在 O(2 n) 中运行。但是，我正在努力分析空间复杂度。
I looked online and had a question on this.
我在网上看了一下，有一个关于这个的问题。
In this Quora thread, the author states that "In your case, you have n stack frames f(n), f(n-1), f(n-2), ..., f(1) and O(1)" . Wouldn't you have 2n stack frames? Say for f(n-2) One frame will be for the actual call f(n-2) but wouldn't there also be a call f(n-2) from f(n-1)?
在此 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) 吗？
采纳答案by committedandroider
If anyone else is still confused, be sure to check out this Youtube video that discusses the space complexity of generating the Fibonacci Sequence. Fibonacci Space Complexity
如果其他人仍然感到困惑，请务必查看此 Youtube 视频，该视频讨论了生成斐波那契数列的空间复杂度。斐波那契空间复杂度
The presenter made it really clear why the space complexity was O(n), the height of the recursive tree is n.
演讲者很清楚为什么空间复杂度是O(n)，递归树的高度是n。
回答by selbie
Here's a hint. Modify your code with a print statement as in the example below:
这是一个提示。使用打印语句修改您的代码，如下例所示：
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);
}
Now execute this line in main:
现在在 main 中执行这一行：
Fibonacci(6,1);
What's the highest value for "stack" that is printed out. You'll see that it's "6". Try other values for "i" and you'll see that the "stack" value printed never rises above the original "i" value passed in.
打印出的“堆栈”的最高值是多少。你会看到它是“6”。尝试为“i”设置其他值，您会看到打印的“stack”值永远不会超过传入的原始“i”值。
Since Fib(i-1) gets evaluated completely before Fib(i-2), there will never be more than ilevels of recursion.
由于 Fib(i-1) 在 Fib(i-2) 之前完全被评估，因此永远不会超过i递归级别。
Hence, O(N).
因此，O(N)。
回答by Richard
As I see it, the process would only descend one of the recursions at a time. The first (f(i-1)) will create N stack frames, the other (f(i-2)) will create N/2. So the largest is N. The other recursion branch would not use more space.
在我看来，该过程一次只会下降一个递归。第一个 (f(i-1)) 将创建 N 个堆栈帧，另一个 (f(i-2)) 将创建 N/2。所以最大的是N。另一个递归分支不会使用更多的空间。
So I'd say the space complexity is N.
所以我会说空间复杂度是 N。
It is the fact that only one recursion is evaluated at a time that allows the f(i-2) to be ignored since it is smaller than the f(i-1) space.
由于 f(i-2) 小于 f(i-1) 空间，因此一次仅计算一次递归允许忽略 f(i-2)。
