这个斐波那契函数有什么问题？

Question

在一篇博客文章中，我偶然发现了这个糟糕的C++代码示例，但没有任何解释为什么它被认为是“糟糕”的。我有自己的想法，但希望听听经验丰富的C++开发人员对此的看法。

unsigned int Fibonacci (unsigned int n)
{
    if (n == 0 || n == 1)
        return n;
    else
        return Fibonacci (n - 1U) + Fibonacci (n - 2U);
}

- Egor Pavlikhin

---

你应该从这个问题中删除"C++"。这个算法真正超越了语言，它与任何实现都不兼容！ - Tom

@Tom，没错，但是可能有一些函数式语言可以很好地优化这个问题。我记得有一些语言可以自动进行记忆化。 - edA-qa mort-ora-y

Answer 1

也许是因为它运行的时间呈指数增长？

- Aaron Klotz

---

这个特定的方法有太多行代码了：return (n < 2) ? n : Fibonacci(n-1U) + Fibonacci(n-2U); 另外，使用闭式方程的主要问题是可能会导致浮点错误。 - Steve Wang

更重要的是，它消耗指数级的CPU堆栈内存（因为递归深度呈指数级增长）。这很糟糕，因为它仅适用于小输入数字。对于较大的数字，由于堆栈溢出而崩溃。 - Serge Dundich

不应该有指数级的堆栈内存，因为C++不会自动并行化。因此，您不会得到超过O(n)的堆栈大小。 - Steve Wang

@Steve Wang：O(n) = O( exp(C*sizeof(n)) ) 是指数级的堆栈大小。虽然这是个好观点，因为我刚意识到运行时间是 O(2^n)=O(exp(C*n))=O(exp(C*exp(C1*sizeof(n)))，实际上是严重超指数级的。真是太可怕了。 :) - Serge Dundich

如果你根据n的位数来计算，那么它的堆栈大小是指数级的..但我认为大家都称之为O(n)。 - Karoly Horvath

Answer 2

为了详细说明上述陈述：由于您没有进行备忘录化，因此在第一次调用时生成2个进程，每个进程都会生成两个进程，以此类推，直到达到基本情况。

避免这种情况的三种方法：1）备忘录化，2）迭代执行，或者3）使用斐波那契数列的闭式方程。 :D

- Steve Wang

---

+1 虽然它们当然不是字面上的“进程”。 - Jon Purdy

嗯，是的。从某种意义上说，它们更像是进程，因为“递归过程”就是一个进程。 - Steve Wang

哇，谢谢你使用“memoize”这个术语。我今天学到了一个新词。 :) - Chris Frederick

Answer 3

斐波那契数列中大多数值都会被计算两次。

例如，Fibonacci(5) 调用了 Fibonacci(4) 和 Fibonacci(3)。

而 Fibonacci(4) 又调用了 Fibonacci(3) 和 Fibonacci(2)。

在这个例子中，可以看到 Fibonacci(3) 被调用了两次。这就是 memoize 可以帮助的地方，但该算法虽然有趣且递归，但并不高效。使用更高效的算法比对低效算法进行 memoize 更可取。

- Paul Beckingham

Answer 4

如果你有足够的时间等待程序运行完成，那么指数级运行时间（甚至可能是超指数级 - 就像这种情况）是可以承受的。

但是没有任何东西能够处理指数级内存消耗 - 特别是指数级程序堆栈消耗（由于递归深度的指数级增长）。对于足够大的输入数字，此程序将因堆栈溢出而崩溃。

并不是说“递归是邪恶的”。 如果递归深度受某个小值的限制（例如，如果它是输入大小的对数或不超过sizeof(int)之类的值），则递归是可接受的。但是当与输入值n成比例时就不行了。

- Serge Dundich

Answer 5

有些人会说这是不好的，因为它使用了递归或者没有使用记忆化，这是相当合理的，因为有一些方法只使用迭代并保存在辅助变量中重复出现的值，其他人则会指出可以使用Binet公式计算到一定程度的精度。

其他人会说这是多个返回点，更奇怪的是，有人可能会说这很糟糕，因为else是多余的，可以删除以节省一行。

- lccarrasco