Go 递归性能问题

Question

开始学习golang，写的一个打印前100个斐比那契数的小程序，但是编译后运行居然巨卡，到30后就十分卡顿，cpu使用99%，但是我的code应该没有问题，不知道原因是什么，ps：C语言1、2秒就输出了。
packagemain
import"fmt"
funcfib(nint)int{
ifn<2{
returnn
}
returnfib(n-2)+fib(n-1)
}
funcmain(){
variint
fori=0;i<100;i++{
fmt.Printf("%d\n",fib(i))
}
}

Answer 1

单步调试发现递归的效率太慢了。fib(100)算了几百万次。递归算法（以计算fib(10)为例）+fib(10)=fib(9)+fib(8)+fib(9)=fib(8)+fib(7)//...可以发现在fib(10)和fib(9)的时候fib(8)被重复计算了。用了一种比较笨的方法，效率还可以。packagemainimport"fmt"funcfib(nuint64)uint64{callTime:=0ifn==0{return0}ifn==1{return1}var(firstuint64=0seconduint64=1resultuint64=0cursoruint64=1)forcursor