以下 Scala 代码在 1.5 分钟内完成，而 GO 中的等效代码在 2.5 分钟内完成。
直到 fib(40) 都需要 2 秒。 fib(50) 出现缺口
我的印象是 GO 是原生的，应该比 Scala 更快。
斯卡拉
def fib(n:Int):Long = {
n match {
case 0 => 0
case 1 => 1
case _ => fib(n-1) + fib(n-2)
}
}
开始
func fib(n int) (ret int) {
if n > 1 {
return fib(n-1) + fib(n-2)
}
return n
}
Scala 优化？
Golang 限制？
正如“My other car is a cadr”所说的那样，问题是“为什么 Scala 在这个特定的微基准测试中比 GO 快？”
忘记斐波那契吧，假设我确实有一个需要递归的函数。
Scala 在递归情况下是否更优越？
它可能是一个内部编译器实现，甚至是 Scala 特定的优化。
知道的请回答。
在 12 秒内循环运行 15000000000
func fib(n int) (two int) {
one := 0
two = 1
for i := 1; i != n; i++ {
one, two = two, (one + two)
}
return
}
最佳答案
对于 Go，使用迭代而不是递归。递归可以用显式堆栈的迭代代替。它避免了函数调用和调用堆栈管理的开销。例如，使用迭代并将 n 从 50 增加到 1000 几乎不需要时间:
package main
import "fmt"
func fib(n int) (f int64) {
if n < 0 {
n = 0
}
a, b := int64(0), int64(1)
for i := 0; i < n; i++ {
f = a
a, b = b, a+b
}
return
}
func main() {
n := 1000
fmt.Println(n, fib(n))
}
输出:
$ time .fib
1000 8261794739546030242
real 0m0.001s
user 0m0.000s
sys 0m0.000s
使用适当的算法。避免指数时间复杂度。当性能很重要时，不要对斐波那契数使用递归。
引用:
Recursive Algorithms in Computer Science Courses: Fibonacci Numbers and Binomial Coefficients
We observe that the computational inefficiency of branched recursive functions was not appropriately covered in almost all textbooks for computer science courses in the first three years of the curriculum. Fibonacci numbers and binomial coefficients were frequently used as examples of branched recursive functions. However, their exponential time complexity was rarely claimed and never completely proved in the textbooks. Alternative linear time iterative solutions were rarely mentioned. We give very simple proofs that these recursive functions have exponential time complexity.
Recursion is an efficient technique for definitions and algorithms that make only one recursive call, but can be extremely inefficient if it makes two or more recursive calls. Thus the recursive approach is frequently more useful as a conceptual tool rather than as an efficient computational tool. The proofs presented in this paper were successfully taught (over a five-year period) to first year students at the University of Ottawa. It is suggested that recursion as a problem solving and defining tool be covered in the second part of the first computer science course. However, recursive programming should be postponed for the end of the course (or perhaps better at the beginning of the second computer science course), after iterative programs are well mastered and stack operation well understood.
关于scala - 递归 GO 与 Scala，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24795294/