在Scala中错误地实现Fibonacci序列
在Scala中错误地实现Fibonacci序列
提问于 2014-06-26 20: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-26 21: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
复制相关文章
点击加载更多
相似问题
组件中存在具有匹配键的绑定: dagger 2.12
Dagger 2.11 -组件中存在具有匹配键的绑定
Dagger 2组件中存在具有匹配键的绑定
匕首:组件中存在具有匹配键的绑定。
Dagger2 -多模块-组件中存在具有匹配密钥的绑定
添加站长 进交流群
领取专属 10元无门槛券
AI混元助手 在线答疑
关注 腾讯云开发者公众号
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
