这种方法是最简单的编程方法，但是由于重复计算的原因，当n>40的以后计算的就会很慢。为了提高计算效率，可以采用下面的递推方法。
2、时间复杂度为O(N)，空间复杂度为O(1)的递推算法
var fibarry = [3]int{0, 1, 0} func fibonacci(n int) int { for i := 2; i <= n; i++ { fibarry[2] = fibarry[0] + fibarry[1] fibarry[0] = fibarry[1] fibarry[1] = fibarry[2] } return fibarry[2] } 这种算法避免了计算机的重复计算，而且占用内存始终为2个单位，相对上一个的递推算法简直是天壤之别，本人在2核 2.4 GHz Intel i5 处理器下计算第1000 000个斐波那契数的用时为3s。那现在有一种问题，还有没有更优的算法呢？如果从计算机的层面考虑是没有，但是数学的能力是无穷的，所以答案是肯定的！3.时间复杂度为O(logN),空间复杂度为O(1)的矩阵递推算法
这个算法主要是根据矩阵和快速幂运算的实现的：
a、矩阵
在线性代数中把f(n)=af(n-1)+bf(n-2)这种递推式称为二阶递推式，所以的递推式都符合(f(n),f(n-1))=(f(n-1),f(n-2))*matrix，这里的matrix就是矩阵，几阶递推式就是几阶的矩阵；斐波那契数列的递推公式是f(n)=f(n-1)+f(n-2)，所以斐波那契数列属于二阶。我们将n带入具体的值： f(3)=f(2)+f(1)→(f(3),f(2))=(f(2),f(1))*(matrix)^1; f(4)=f(3)+f(2)→(f(4),f(3))=(f(3),f(2))*(matrix)^1=(f(2),f(1))*(matrix)^2; ..... f(n+1)=(f(2),f(1))*(matrix)^n-1→(f(n+1),f(n))=(f(2),f(1))*(matrix)^n-1=(f(1),f(0))*(matrix)^n; 根据这些公式可以算出二阶的matrix={{1，1}，{1，0}};
这样就将问题转化为如何计算矩阵的n次幂了。由于golang的标准库中没有matrix库，所以自己简单的封装了一个，代码如下：
package matrix import ( "math/big" ) type Matrix struct { rows, columns int // the number of rows and columns. data []*big.Int // the contents of the matrix as one long slice. } // Set lets you define the value of a matrix at the given row and // column. func (A *Matrix) Set(r int, c int, val *big.Int) { A.data[findIndex(r, c, A)] = val } // Get retrieves the contents of the matrix at the row and column. func (A *Matrix) Get(r, c int) *big.Int { return A.data[findIndex(r, c, A)] } // Column returns a slice that represents a column from the matrix. // This works by examining each row, and adding the nth element of // each to the column slice. func (A *Matrix) Column(n int) []*big.Int { col := make([]*big.Int, A.rows) for i := 1; i <= A.rows; i++ { col[i-1] = A.Row(i)[n-1] } return col } // Row returns a slice that represents a row from the matrix. func (A *Matrix) Row(n int) []*big.Int { return A.data[findIndex(n, 1, A):findIndex(n, A.columns+1, A)] } // Multiply multiplies two matrices together and return the resulting matrix. // For each element of the result matrix, we get the dot product of the // corresponding row from matrix A and column from matrix B. func Multiply(A, B Matrix) *Matrix { C := Zeros(A.rows, B.columns) for r := 1; r <= C.rows; r++ { A_row := A.Row(r) for c := 1; c <= C.columns; c++ { B_col := B.Column(c) C.Set(r, c, dotProduct(A_row, B_col)) } } return &C } // Identity creates an identity matrix with n rows and n columns. When you // multiply any matrix by its corresponding identity matrix, you get the // original matrix. The identity matrix looks like a zero-filled matrix with // a diagonal line of one's starting at the upper left. func Identity(n int) Matrix { A := Zeros(n, n) for i := 0; i < len(A.data); i += (n + 1) { A.data[i] = big.NewInt(1) } return A } // Zeros creates an r x c sized matrix that's filled with zeros. The initial // state of an int is 0, so we don't have to do any initialization. func Zeros(r, c int) Matrix { return Matrix{r, c, make([]*big.Int, r*c)} } // New creates an r x c sized matrix that is filled with the provided data. // The matrix data is represented as one long slice. func New(r, c int, data []*big.Int) Matrix { if len(data) != r*c { panic("[]*big.Int data provided to matrix.New is great than the provided capacity of the matrix!'") } A := Zeros(r, c) A.data = data return A } // findIndex takes a row and column and returns the corresponding index // from the underlying data slice. func findIndex(r, c int, A *Matrix) int { return (r-1)*A.columns + (c - 1) } // dotProduct calculates the algebraic dot product of two slices. This is just // the sum of the products of corresponding elements in the slices. We use // this when we multiply matrices together. func dotProduct(a, b []*big.Int) *big.Int { total := new(big.Int) x := new(big.Int) z := new(big.Int) for i := 0; i < len(a); i++ { y := x.Mul(a[i], b[i]) total = z.Add(total, y) // total = total.Add(total, total.Mul(a[i], b[i])) } return total }
b、快速幂运算
对于a^b，可将b转化为二进制，即b=b0+b1*2+b2*2^2+...+bn*2^n ,这里我们的b0对应的是b二进制的第一位,那么我们的a^b运算就可以拆解成a^b0*a^b1*2*...*a^(bn*2^n),对于b来说，二进制位不是0就是1，那么对于bx为0的项我们的计算结果是1就不用考虑了，我们真正想要的其实是b的非0二进制位,那么除去了b的0的二进制位之后我们得到的式子是a^(bx*2^x)*...*a(bn*2^n),通过这种方法，可以在O(lbn)的时间内计算出a的n次幂，这就是快速幂运算的本质所在。代码如下：
for b > 0 { if b&1 == 1 { s = *matrix.Multiply(s, a) b = b >> 1 } else { b = b >> 1 } a = *matrix.Multiply(a, a) } return s }基于上面的矩阵和快速幂，完整代码如下：
package main import ( "fmt" "math/big" "time" "util/matrix" ) //求矩阵的n次幂 func MatPow(a matrix.Matrix, b int) matrix.Matrix { arr0 := [4]*big.Int{big.NewInt(1), big.NewInt(0), big.NewInt(0), big.NewInt(1)} s := matrix.New(2, 2, arr0[0:4]) for b > 0 { if b&1 == 1 { s = *matrix.Multiply(s, a) b = b >> 1 } else { b = b >> 1 } a = *matrix.Multiply(a, a) } return s } //矩阵的N次幂与fib(1)和Fib(0)组成的2行1列的矩阵相乘求fib(n+1)和Fib(n)组成的2行1列的矩阵 //从fib(n+1)和Fib(n)的2行1列的矩阵中取出fib(n) func Fib(n int) *big.Int { arr0 := [6]*big.Int{big.NewInt(1), big.NewInt(1), big.NewInt(1), big.NewInt(0), big.NewInt(2), big.NewInt(1)} k := matrix.New(2, 2, arr0[0:4]) s := MatPow(k, n) d := matrix.New(2, 1, arr0[0:2]) s = *matrix.Multiply(s, d) return s.Get(2, 1) } func main() { start := time.Now() n := 1000000 m := Fib(n) fmt.Println("f(n)的结果是", m) end := time.Now() delta := end.Sub(start) fmt.Printf("longCalculation took this amount of time: %s\n", delta) } 基于这个算法，本人在2核 2.4 GHz Intel i5 处理器下计算第1000 000个斐波那契数的用时为305ms,计算性能又提升了1000倍，所以数学的力量是无穷的！
