在一篇博客文章中,我偶然发现了这个糟糕的C++代码示例,但没有任何解释为什么它被认为是“糟糕”的。我有自己的想法,但希望听听经验丰富的C++开发人员对此的看法。
unsigned int Fibonacci (unsigned int n)
{
if (n == 0 || n == 1)
return n;
else
return Fibonacci (n - 1U) + Fibonacci (n - 2U);
}
在一篇博客文章中,我偶然发现了这个糟糕的C++代码示例,但没有任何解释为什么它被认为是“糟糕”的。我有自己的想法,但希望听听经验丰富的C++开发人员对此的看法。
unsigned int Fibonacci (unsigned int n)
{
if (n == 0 || n == 1)
return n;
else
return Fibonacci (n - 1U) + Fibonacci (n - 2U);
}
return (n < 2) ? n : Fibonacci(n-1U) + Fibonacci(n-2U);
另外,使用闭式方程的主要问题是可能会导致浮点错误。 - Steve WangO(n) = O( exp(C*sizeof(n)) )
是指数级的堆栈大小。虽然这是个好观点,因为我刚意识到运行时间是 O(2^n)=O(exp(C*n))=O(exp(C*exp(C1*sizeof(n)))
,实际上是严重超指数级的。真是太可怕了。 :) - Serge Dundich斐波那契数列中大多数值都会被计算两次。
例如,Fibonacci(5) 调用了 Fibonacci(4) 和 Fibonacci(3)。
而 Fibonacci(4) 又调用了 Fibonacci(3) 和 Fibonacci(2)。
在这个例子中,可以看到 Fibonacci(3) 被调用了两次。这就是 memoize 可以帮助的地方,但该算法虽然有趣且递归,但并不高效。使用更高效的算法比对低效算法进行 memoize 更可取。
如果你有足够的时间等待程序运行完成,那么指数级运行时间(甚至可能是超指数级 - 就像这种情况)是可以承受的。
但是没有任何东西能够处理指数级内存消耗 - 特别是指数级程序堆栈消耗(由于递归深度的指数级增长)。对于足够大的输入数字,此程序将因堆栈溢出而崩溃。
并不是说“递归是邪恶的”。 如果递归深度受某个小值的限制(例如,如果它是输入大小的对数或不超过sizeof(int)之类的值),则递归是可接受的。但是当与输入值n成比例时就不行了。
有些人会说这是不好的,因为它使用了递归或者没有使用记忆化,这是相当合理的,因为有一些方法只使用迭代并保存在辅助变量中重复出现的值,其他人则会指出可以使用Binet公式计算到一定程度的精度。
其他人会说这是多个返回点,更奇怪的是,有人可能会说这很糟糕,因为else是多余的,可以删除以节省一行。