斐波那契数列一般都用于介绍递归的思想。
我们知道斐波那契数列的通项公式（n>1）如下：
F(n) = F(n-1) + F(n-2)
按照这个公式写个代码就很容易了：
int fibonacci(int n) {
if (n == 0 || n == 1) {
return n;
}
return fibonacci(n-1) + fibonacci(n-2);
}
这种代码简单又优雅，但是缺点也很明显，就是慢：
又慢又占空间。
这是为什么呢？
我们来看看递归都做了什么，以n=5为例，如下图：
这里会有很多的重复计算过程，这个重复计算的过程叫做递归栈，递归最大的毛病就是递归栈里重复的东西太多。
观察上图，如果从下向上，效果会更加的好，可以借助数组来实现，我们知道斐波那契数列其实就是这样的一个数列：
0，1，1，2，3，5，8...
只要将第一和第二项算出来保存在数组中，后面的项就很好计算了：
public int Fibonacci2(int n) {
int[] fib = new int[45];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
n=5的时候，这个数组最终是这样的[0,1,1,2,3,5,......]，此时的时间复杂度仅仅是O(n)，比递归的O(2^n)好太多了：
仅仅消耗了17ms，是原先的5.8%左右。
但是，继续观察上面的数组：
[0, 1, 1, 2, 3, 5]，我们会发现这个数组中，f(0）和f(2)并没有用到，这两个其实可以精简掉，于是代码变成了这样：
public int Fibonacci(int n) {
if (n == 0 || n == 1) {
return n;
}
int a = 0;
int b = 1;
int c = 0;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
n=5的情况下，这个循环只会计算f(1),f(3),f(4)和f(5)的值，并不用数组去保存，因此空间也节省了下来。
另外我试了试C和Java语言用第三种解法的速度差异，发现C语言还是很有优势的：
同样的算法竟然只用了5ms。