fibonacci 数列算是不管哪个语言里头都能碰到的一个问题，其过于经典，导致其有很多解法，大体上可以归为遍历，递归，优化的递归，矩阵（矩阵这个确实很厉害）。

什么是 斐波那契数列？ 0,1,1,2,3,5,8 … 除了1和2以外，剩下的数都满足 f(n) = f(n-2)+f(n-1)。

递归方式：

1
2
3
4
5
6
7
8
9
// 递归的方式 - 时间复杂度 O(2^n)
func fibonacciRecusive(num int) int {

	if num == 1 || num == 2 {
		return 1
	}

	return fibonacciRecusive(num-1) + fibonacciRecusive(num-2)
}

改进递归方式：

使用map保存计算结果，相当于对已经计算过的数，避免计算第二次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 时间复杂度 O(n)
var resultMap = make(map[int]int)

func fibonacciRecusiveMem(num int) int {
	if val, ok := resultMap[num]; ok {
		return val
	}

	if num == 1 || num == 2 {
		return 1
	}

	result := fibonacciRecusive(num-1) + fibonacciRecusive(num-2)
	resultMap[num] = result
	return result
}

遍历的方式：

1
2
3
4
5
6
7
8
9
10
11
12
// 时间复杂度 O(n)
func fibonacciIterative(num int) int {
	var f = []int{
		0, 1,
	}

	for i := 2; i <= num; i++ {
		f = append(f, f[i-1]+f[i-2])
	}

	return f[num]
}

还有个矩阵的方式，这个建议直接搜索其他文章，因为光看代码完全不好懂，还是得伴着原理一起下饭。