Go 递归性能问题

Question

开始学习golang，写的一个打印前100个斐比那契数的小程序，但是编译后运行居然巨卡，到30后就十分卡顿，cpu使用99%，但是我的code应该没有问题，不知道原因是什么，ps：C语言1、2秒就输出了。packagemainimport"fmt"funcfib(nint)int{ifn

Answer 1

单步调试发现递归的效率太慢了。fib(100)算了几百万次。
递归算法（以计算fib(10)为例）
+fib(10)=fib(9)+fib(8)
+fib(9)=fib(8)+fib(7)
//...
可以发现在fib(10)和fib(9)的时候fib(8)被重复计算了。
用了一种比较笨的方法，效率还可以。
packagemain
import"fmt"
funcfib(nuint64)uint64{
callTime:=0
ifn==0{
return0
}
ifn==1{
return1
}
var(
firstuint64=0
seconduint64=1
resultuint64=0
cursoruint64=1
)
forcursorcallTime++
fmt.Println("fib",callTime)
result=first+second
first=second
second=result
cursor++
}
returnresult
}
var(
callTime=0
)
funcfib2(nint)int{
callTime++
fmt.Println("fib2",callTime)
ifn<=0{
return0
}
ifn==1{
return1
}
returnfib2(n-1)+fib2(n-2)
}
funcmain(){
fib(10)
fib2(10)
}
终端输出
fib1
fib2
fib3
fib4
fib5
fib6
fib7
fib8
fib9
fib21
fib22
fib23
fib24
fib25
fib26
fib27
fib28
fib29
fib210
fib211
fib212
fib213
fib214
fib215
fib216
fib217
fib218
fib219
fib220
fib221
fib222
fib223
fib224
fib225
fib226
fib227
fib228
fib229
fib230
fib231
fib232
fib233
fib234
fib235
fib236
fib237
fib238
fib239
fib240
fib241
fib242
fib243
fib244
fib245
fib246
fib247
fib248
fib249
fib250
fib251
fib252
fib253
fib254
fib255
fib256
fib257
fib258
fib259
fib260
fib261
fib262
fib263
fib264
fib265
fib266
fib267
fib268
fib269
fib270
fib271
fib272
fib273
fib274
fib275
fib276
fib277
fib278
fib279
fib280
fib281
fib282
fib283
fib284
fib285
fib286
fib287
fib288
fib289
fib290
fib291
fib292
fib293
fib294
fib295
fib296
fib297
fib298
fib299
fib2100
fib2101
fib2102
fib2103
fib2104
fib2105
fib2106
fib2107
fib2108
fib2109
fib2110
fib2111
fib2112
fib2113
fib2114
fib2115
fib2116
fib2117
fib2118
fib2119
fib2120
fib2121
fib2122
fib2123
fib2124
fib2125
fib2126
fib2127
fib2128
fib2129
fib2130
fib2131
fib2132
fib2133
fib2134
fib2135
fib2136
fib2137
fib2138
fib2139
fib2140
fib2141
fib2142
fib2143
fib2144
fib2145
fib2146
fib2147
fib2148
fib2149
fib2150
fib2151
fib2152
fib2153
fib2154
fib2155
fib2156
fib2157
fib2158
fib2159
fib2160
fib2161
fib2162
fib2163
fib2164
fib2165
fib2166
fib2167
fib2168
fib2169
fib2170
fib2171
fib2172
fib2173
fib2174
fib2175
fib2176
fib2177
可以看到算法1优势还是蛮大的