在观看了麻省理工学院关于动态编程的讲座后，我想用斐波那契进行一些练习。我首先编写了幼稚的递归实现，然后添加了记忆。以下是备忘录版本：
package main
import (
"fmt"
)
func fib_memoized(n int, memo map[int]int64) int64 {
memoized, ok := memo[n]
if ok {
return memoized
}
if n < 2 {
return int64(n)
}
f := fib_memoized(n-2, memo) + fib_memoized(n-1, memo)
memo[n] = f
return f
}
func main() {
memo := make(map[int]int64)
for i := 0; i < 10000; i++ {
fmt.Printf("fib(%d) = %d\n", i, fib_memoized(i, memo))
}
}
然后，我继续编写该程序的非递归版本：
package main
import (
"fmt"
)
func fib(n int) int64 {
var f1 int64 = 1
var f2 int64 = 0
for i := 0; i < n; i++ {
f1, f2 = f2, f1+f2
}
return f2
}
func main() {
for i := 0; i < 10000; i++ {
fmt.Printf("fib(%d) = %d\n", i, fib(i))
}
}
令我感到困惑的是，记忆化版本似乎至少与非递归版本一样好，有时甚至优于它。当然，我期望备忘录与朴素的递归实现相比带来很大的改进，但我只是无法弄清楚为什么/如何备忘录化版本可以与之相提并论，甚至超过其非递归版本。
我确实尝试过查看两个版本的汇编输出（通过）获得，但无济于事。我仍然在备忘录版本中看到说明，在我看来，这应该会产生足够的开销来证明它至少略优于非递归版本。go tool compile -SCALL
任何知识渊博的人可以帮助我了解发生了什么吗？
附言：我知道整数溢出;我使用10000只是为了增加负载。
白衣非少年
慕哥6287543
慕妹3242003
相关分类