斐波那契数列
描述
查找斐波纳契数列中第 N 个数。
所谓的斐波纳契数列是指：
前2个数是 0 和 1 。
第 i 个数是第 i-1 个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
样例
给定 1，返回 0
给定 2，返回 1
给定 10，返回 34
思路
斐波那契数列算是一个很常见的典型递归问题了，直接就可以很轻松地根据定义写出代码：
public int fibonacci(int n) {
// write your code here
if (n == 1) return 0;
if (n == 2) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
然而得到的结果却是Time Limit Exceeded
显然，问题自然是出在递归的身上，于是开始分析一下：
递归算法在程序中运行的时候会占用不少的栈空间，这一点是毋庸置疑的，但是这并不是最大的问题，最大的问题是这个代码中存在大量的重复计算。
当n > 2时，在计算f(n)显然会计算f(n - 1) + f(n - 2)，当计算完f(n - 1)后，程序又会从头开始计算f(n - 2)，然而事实是f(n - 2)在计算f(n - 1)的过程中就已经知道结果了，程序却从头算起，这就造成了重复计算。当n数值小的时候并不要紧，一旦n的数据越来越大，所浪费的时间也就越来越多，这也就是这次超时的根本所在。
知道问题后，我们就很容易能想出对策了，既然已经算出了值却没有使用，那么我们可以将算出的结果保存起来，方便下次或者将来的使用。这里我选择了使用List来存放计算的结果，代码如下：
代码
class Solution {
/**
* @param n: an integer
* @return an integer f(n)
*/
public int fibonacci(int n) {
// write your code here
List<Integer> list = new ArrayList<Integer>();
list.add(0);
list.add(1);
for (int i = 0; i < n; i++) {
if (list.size() < (i + 1)) {
list.add(list.get(i - 1) + list.get(i - 2));
}
}
return list.get(n - 1);
}
}
写在最后
递归算法因为其结构清晰，所以阅读起来更容易理解，但是却往往带来性能上的缺失。
因此，在写出递归算法后，应尽量考虑是否还有可优化的空间。
比如这次的题目，当n越来越大，其带来的性能损耗将会是非常可怕的。
最近在看动态规划的时候，也体会到了这种思想。