Go 递归性能问题

Question

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

package main

import "fmt"

func fib (n int) int {
    if n < 2 {
        return n
    }
    return fib(n-2) + fib(n-1)
}

func main() {
    var i int
    for i=0; i<100; i++ {
        fmt.Printf("%d\n", fib(i))
    }
}

Answer 1

可以 闭包 实现， 很快的

package main

import (
    "fmt"
    "math/big"
)

func fibonacci() func() *big.Int {
    v, s := big.NewInt(0), big.NewInt(1)
    return func() *big.Int {
        var tmp big.Int
        tmp.Set(s)
        s.Add(s,v)
        v = &tmp
        return s
    }
}

func main() {
    var r *big.Int
    f := fibonacci()
    for i := 0; i < 10000; i++ {
        r = f()
    }
    fmt.Println(r)
}

其实官方tour里面有示例的
go tour

Answer 2

单步调试发现递归的效率太慢了。fib(100)算了几百万次。

递归算法（以计算fib(10)为例）

+ fib(10)=fib(9)+fib(8)
+ fib(9)=fib(8)+fib(7)
// ...

可以发现在fib(10)和fib(9)的时候fib(8)被重复计算了。

用了一种比较笨的方法，效率还可以。

package main

import "fmt"

func fib(n uint64) uint64 {
    callTime := 0
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    var (
        first  uint64 = 0
        second uint64 = 1
        result uint64 = 0
        cursor uint64 = 1
    )
    for cursor < n {
        callTime++
        fmt.Println("fib", callTime)
        result = first + second
        first = second
        second = result
        cursor++
    }
    return result
}

var (
    callTime = 0
)

func fib2(n int) int {
    callTime++
    fmt.Println("fib2", callTime)
    if n <= 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    return fib2(n-1) + fib2(n-2)
}
func main() {
    fib(10)
    fib2(10)
}

终端输出

fib 1
fib 2
fib 3
fib 4
fib 5
fib 6
fib 7
fib 8
fib 9
fib2 1
fib2 2
fib2 3
fib2 4
fib2 5
fib2 6
fib2 7
fib2 8
fib2 9
fib2 10
fib2 11
fib2 12
fib2 13
fib2 14
fib2 15
fib2 16
fib2 17
fib2 18
fib2 19
fib2 20
fib2 21
fib2 22
fib2 23
fib2 24
fib2 25
fib2 26
fib2 27
fib2 28
fib2 29
fib2 30
fib2 31
fib2 32
fib2 33
fib2 34
fib2 35
fib2 36
fib2 37
fib2 38
fib2 39
fib2 40
fib2 41
fib2 42
fib2 43
fib2 44
fib2 45
fib2 46
fib2 47
fib2 48
fib2 49
fib2 50
fib2 51
fib2 52
fib2 53
fib2 54
fib2 55
fib2 56
fib2 57
fib2 58
fib2 59
fib2 60
fib2 61
fib2 62
fib2 63
fib2 64
fib2 65
fib2 66
fib2 67
fib2 68
fib2 69
fib2 70
fib2 71
fib2 72
fib2 73
fib2 74
fib2 75
fib2 76
fib2 77
fib2 78
fib2 79
fib2 80
fib2 81
fib2 82
fib2 83
fib2 84
fib2 85
fib2 86
fib2 87
fib2 88
fib2 89
fib2 90
fib2 91
fib2 92
fib2 93
fib2 94
fib2 95
fib2 96
fib2 97
fib2 98
fib2 99
fib2 100
fib2 101
fib2 102
fib2 103
fib2 104
fib2 105
fib2 106
fib2 107
fib2 108
fib2 109
fib2 110
fib2 111
fib2 112
fib2 113
fib2 114
fib2 115
fib2 116
fib2 117
fib2 118
fib2 119
fib2 120
fib2 121
fib2 122
fib2 123
fib2 124
fib2 125
fib2 126
fib2 127
fib2 128
fib2 129
fib2 130
fib2 131
fib2 132
fib2 133
fib2 134
fib2 135
fib2 136
fib2 137
fib2 138
fib2 139
fib2 140
fib2 141
fib2 142
fib2 143
fib2 144
fib2 145
fib2 146
fib2 147
fib2 148
fib2 149
fib2 150
fib2 151
fib2 152
fib2 153
fib2 154
fib2 155
fib2 156
fib2 157
fib2 158
fib2 159
fib2 160
fib2 161
fib2 162
fib2 163
fib2 164
fib2 165
fib2 166
fib2 167
fib2 168
fib2 169
fib2 170
fib2 171
fib2 172
fib2 173
fib2 174
fib2 175
fib2 176
fib2 177

可以看到算法1优势还是蛮大的

Answer 3

放个数组保存中间结果,没有时再算

package main

import "fmt"

const count=100
var res[count] int64


func fib (n int64) int64 {
    if res[n] > 0 {return res[n] }
    if n < 2 {
        res[n] = n
        return n
    }
    res[n] =  fib(n-2) + fib(n-1)
    return res[n]
}

func main() {
    var i int64
    for i=0; i<count; i++ {
        fmt.Printf("%d: %d\n", i,fib(i))
    }
}

只是int64也太小, 算到大概92时溢出了.

在线演示
http://tpcg.io/970xwW

其实中间结果也不需要这么大数组,因为是顺序执行,如果只算特定一个数的话,只用两个数中间变量也能实现.

简单粗暴就是好.

Answer 4

那一定是你的 C 代码写错了