这个斐波那契函数有什么问题？
在一篇博客文章中偶然发现了这个糟糕的 C++ 代码示例，但没有任何解释为什么它被认为是“糟糕的”。我有自己的想法，但想听听经验丰富的 C++ 开发人员对此的看法。
unsigned int Fibonacci (unsigned int n)
{
if (n == 0 || n == 1)
return n;
else
return Fibonacci (n - 1U) + Fibonacci (n - 2U);
}
Stumbled upon this example of bad C++ code in a blog post, without any explanation as to why it is considered "bad". I have my own ideas, but would like to hear experienced C++ devs on this.
unsigned int Fibonacci (unsigned int n)
{
if (n == 0 || n == 1)
return n;
else
return Fibonacci (n - 1U) + Fibonacci (n - 2U);
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
也许是因为它以指数时间运行？
Perhaps because it runs in exponential time?
详细说明上面的说法：由于您没有记忆，因此您在第一次调用时会生成 2 个进程，并且每个进程都会生成两个进程，依此类推，直到达到基本情况为止。
避免这种情况的三种方法：1) 记忆，2) 迭代，或 3) 使用斐波那契序列的封闭形式方程。 ：D
To elaborate on the above statement: since you're not memoizing, you spawn 2 processes with the first call, and each of those spawns two processes, and so forth down the chain until you hit the base case.
Three ways to avoid this: 1) Memoize, 2) Do it iteratively, or 3) Use the closed form equation for the Fibonacci sequence. :D
大多数斐波那契 (n) 值都会计算两次。
例如，Fibonacci(5) 调用 Fibonacci(4) 和 Fibonacci(3)。
Fibonacci(4) 依次调用 Fibonacci(3) 和 Fibonacci(2)。
看看这个例子中的 Fibonacci(3) 是如何被调用两次的？这就是 memoize 会有所帮助的地方，但是该算法虽然有趣且递归，但效率不高。最好使用一种更有效的算法，而不是记住一种低效的算法。
Most values of Fibonnacci (n) are calculated twice.
For example, Fibonacci(5) calls Fibonacci(4) and Fibonacci(3).
That Fibonacci(4) in turn calls Fibonacci(3) and Fibonacci(2).
See how Fibonacci(3) in this example is called twice? That's where the memoize would help, but the algorithm, while interesting and recursive, is not efficient. It would be preferable to use a more efficient algorithm than to memoize an inefficient one.
如果您有永恒的时间等待程序完成，那么指数运行时间（甚至可能是超指数 - 就像在本例中）是可以忍受的。
但世界上没有任何东西可以处理指数内存消耗 - 特别是指数程序堆栈消耗（由于递归的指数深度）。该程序将因输入数量足够大而导致堆栈溢出而崩溃。
这不像“递归是邪恶的”。
如果递归深度受到某个小值的限制（例如，如果它是输入大小的对数或不大于 sizeof(int) 或其他值），则递归是可接受的。但当与输入值 n 成比例时则不然。
Exponential running time (and may be even super-exponential - like in this case) is bearable if you have like eternity to wait until program finishes.
But nothing in the world can possibly handle exponential memory consumption - especially exponential program stack consumption (due to exponential depth of recursion). This program will just crash because of stack overflow with big enough input number.
It is not like "recursion is evil".
Recursion is acceptable if the depth of recursion is limited by some small value (e.g. if it is logarithmic of the input size or not more than sizeof(int) or something). But not when proportional to the input value
n.有些人会说它不好，因为它使用递归或者因为它在没有记忆的情况下使用它，这是相当合理的，因为有些方法只使用迭代并保存在辅助变量中重复的值，其他人会指出它可以使用比奈公式计算，具有一定的精度。
其他人会说这是多个返回点，更奇怪的是有人可能会说这不好，因为 else 是多余的，可以删除它以节省一行。
Some people will say it's bad because it uses recursion or because it uses it without memoization, which is quite reasonable since there are approaches that only use iteration and save values that would be repeated in auxiliary variables, other will point to the fact that it can be calculated using Binet's Formula, to a certain degree of precision.
Other people will say it's the multiple return points, and even more strangely someone might say it's bad because the else is superfluous and it could be removed to save one line.