再帰したって速いフィボナッチは書けるよ
Goってポリシーとして末尾最適しないからfibそんな速くないでしょ、みたいなクソリプを思いついてしまったのでエアリプ。
package main
import "fmt"
func main() {
fmt.Println(fib(40))
}
func fib2(n uint64) (uint64, uint64) {
if n == 1 {
return 1, 0
}
prev, prevprev := fib2(n - 1)
return prev + prevprev, prev
}
func fib(n uint64) uint64 {
f, _ := fib2(n)
return f
}
2つ値を返せばいい。
% time ./fib
102334155
./fib 0.00s user 0.00s system 18% cpu 0.027 total
速い！