在Scala中错误地实现Fibonacci序列
在Scala中错误地实现Fibonacci序列
提问于 2014-06-27 04:59:20
在一次斯卡拉会议上，我们在讨论“斯卡拉方式”.
有人问另一个开发人员如何在Scala中实现Fibonacci序列.该人回答如下代码(只被告知，虽然它工作，但它不是最优的)：
def fibonacci(n: Int):BigInt = n match {
case 0 => 0
case 1 => 1
case _ => fibonacci(n - 1) + fibonacci(n - 2)
}- 这个方法有什么问题？
- 改进这段代码的方法是什么，Scala方法？
回答 1
Stack Overflow用户
发布于 2014-06-27 05:10:00
这一个将计算许多子问题不止一次。你可以把算法想象成一棵树。
例如，如果您请求fibonacci(4)，则计算：
fib(4) = fib(3) + fib(2) = 2 + 1 = 3
// left subtree:
fib(3) = fib(2) + fib(1) = 1+1 = 2
// left
fib(2) = fib(1) + fib(0) = 0+1 = 1
// right
fib(1) = 1
// right
fib(2) = fib(1) + fib(0) = 0+1 = 1正如你所看到的，你计算fib(2) 2次，这只会在更高的数字上变得更糟。
至于如何改进此代码：
- 要么回忆录价值
- 使用动态编程的技巧(嗯，或多或少也是回忆录)
- 或者使用更好的算法！
这里已经有很多关于这个主题的问题了--从这里开始：Fibonacci级数的有效计算
或者看一下scala特有的答案：在Scala中编写Fibonacci函数的最快方法是什么？
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/24444250
复制相关文章
相似问题
腾讯云开发者
