定义

首先介绍一下什么是菲波那切数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。 – 百度百科

这么一个来自大自然的公式，和植物的花瓣，蜂巢，蜻蜓翅膀都能找到它的身影。说明上天造物也是有迹可循的。

回到正题，这个公司可以简单的用一句话概括：

第N个数，是由N-1位置的数加上N-2位置的数得来的。并且第0个数是0，第1个数是1。

也就是说在没有通项式的情况下，要想知道一个数，必须得算出它前面的所有数。

下面就实现几种方法来计算斐波那契数列

使用递归

说起这个算法，很多人自然想起的是递归，很多编程教程在讲到函数这一块的时候，会提起递归，而计算菲波那切数列似乎成了一个完美的例子。

让我们来看一下计算菲波那切数列的公式：
F(n) = F(n-1)+F(n-2)

那F(n-1)怎么算呢？一样的
F(n-1) = F((n-1) - 1)+F((n-1)-2)

我们只需要将n替换一下就可以了，也就是说同样的函数逻辑适用于所有数列项。

func Fibonacci(n int) (res int) {
	if n <= 1 {
		res = n
	} else {
		res = Fibonacci(n-1) + Fibonacci(n-2)
	}
	return
}

首先这里

if n <= 1 {
	res = n
}

是初始化前两个数n0 = 0，n1 = 1，之后的所有数都是通过公式来得出的。

使用循环

使用递归很简单，只需要应用公式就好了，但是递归有一个很致命的缺点，就是函数调用栈。递归会将每个函数都推入函数栈中，因为不会马上执行。这就使得函数栈会根据计算量一直膨胀，最后导致栈溢出。所以有些语言也对递归做了些优化，比如尾递归。
那么更直接的就是不使用递归而使用循环，那么就只有一个函数调用。可能你也听过一句话叫做所有递归都能被写成循环。

func Fibonacci2(n int) (res int64) {
	cache := map[int]int64{
		0: 0,
		1: 1,
	}

	for i := 2; i <= n; i++ {
		cache[i] = cache[i-1] + cache[i-2]
	}
	res = cache[n]
	return
}

使用闭包

使用闭包的原理就在于返回函数，该函数中存有上两个数的作用域，可计算出当前N的值，并且返回带有下两个数作用域的函数。

func Fibonacci3(n int) (res int64) {
	if n <= 1 {
		res = int64(n)
		return
	}

	inner := func() func() int64 {
		a1, a2 := int64(0), int64(1)
		return func() int64 {
			_a2 := a2
			a2 = a1 + a2
			a1 = _a2
			return a2
		}
	}

	fib := inner()

	for i := 2; i <= n; i++ {
		res = fib()
	}

	return
}

这里的inner函数，调用之后就初始化了F(0)和F(1)的值，这两个值都在返回的函数fib的作用域里（闭包）。
当调用一次fib之后，将F(0)加上F(1)得出F(2)，并将F(1)和F(0)改存为F(2)和F(1)。然后返回F(2)。这样在下一次调用的时候，就会计算F(3)的值，想要获取第N项的值，那就得调用N-1次fib函数。

性能

最后让我们来测试下以上方法的性能表现怎么样，这里使用的是GO自带的基准测试

go test -bench=. -benchmem ./fibonacci

首先我们看看N=10的性能

方法	循环次数	单次耗时	单次内存消耗
递归	3223458	406 ns/op	0 B/op
循环	1650480	611 ns/op	302 B/op
闭包	12316435	92.7 ns/op	48 B/op

再来看N=20时的表现

方法	循环次数	单次耗时	单次内存消耗
递归	24525	52144 ns/op	0 B/op
循环	550345	2131 ns/op	966 B/op
闭包	9536547	122 ns/op	48 B/op

可以看到递归随着N的增加耗时是剧增，而循环方法也是翻了两倍。但是可以看到，闭包方法却十分稳定！无论是耗时或者是内存消耗都处于极其优秀的水平。

优化

尾递归

在有用尾递归优化的语言中，递归的的例子可以改写为

func Fibonacci(n int) int64 {
	if n <= 1 {
		return int64(n)
	}

	return Fibonacci(n-1) + Fibonacci(n-2)
}

但是经测试，得出来的结果是一样的，也就是说golang没有做尾递归优化。所以小伙伴们在用递归的时候还是得注意小心栈溢出。

循环优化

在上面用循环的例子里，我们看到它居然跑不过闭包函数调用！原因呢，其实在于我们有一个map的操作。初始化和操作map的时间也是非常长的(相对于操作变量来说)。并且我们把所有的中间结果都存了下来，实事证明呢其实没必要，因为每个中间值只用到一两次并且用完即扔。

优化后的代码

func Fibonacci2_(n int) (res int64) {
	if n <= 1 {
		res = int64(n)
		return
	}

	a1, a2 := int64(0), int64(1)

	for i := 2; i <= n; i++ {
		a1, a2 = a2, a1+a2
	}
	res = a2
	return
}

N=20时的表现

方法	循环次数	单次耗时	单次内存消耗
循环优化	74500066	14.9 ns/op	0 B/op

果然性能之王for循环，无敌！