经典就是经典，不论多少年，经典永远不会改变。
语言，框架总有一天会过时，但是唯独经典永远存在。这就是研究这些经典算法的永恒。
当我这样一个.net程序员去应聘Java, C++, Android岗位时，我发现框架语言特性，都被抛弃。就这样海绵一挤，我的4年水分就出来了。剩下的精华已不多。而能贯穿各个岗位的，就是这些虽在身边，但却忽视如空气般的，底层知识和应用能力。
你的经验，有多少水分呢？在一个公司久了，出来晒晒，你就发现，其实你会的并不多。
有趣问题：
1，有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?
答：这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有一种登法；登上三级台阶，有两种登法；登上四级台阶，有三种方法……所以，1, 1，2，3，5，8，13……登上十级，有89种。
2，数列中相邻两项的前项比后项的极限是多少，就是问，当n趋于无穷大时，F(n)/F(n+1)的极限是多少？
答：这个可由它的通项公式直接得到，极限是(-1+√5)/2，这个就是所谓的黄金分割点，也是代表大自然的和谐的一个数字。
数学表示：
Fibonacci数列的数学表达式就是：
F(n) = F(n-1) + F(n-2)
F(1) = 1
F(2) = 1
公式是给出来了，可是为什么是这个公式呢？你有没有想过？
公式是怎么提炼出来的？我数学不好，所以我的经验就是从找规律开始：
如果起点是0的话，对于第一级台阶来讲有F(1)=1种走法，对于第二级来讲有F(2)=1种走法。对于第三极台阶，有1+2, 2+1两种走法。对于第四级台阶，可以从第三极台阶+1，也可以从第二级台阶+2，也就是F(4) = F(3) + F(2)，以此类推。
写代码也很简单：
///<summary>
/// Fibonacci递归算法。时间复杂度O(n)=O((3/2)^n)，指数级算法
///</summary>
public ulong FibonacciRecursion(int n)
{
if (n < 0)
throw new ArgumentOutOfRangeException("n must > 0.");
if (n == 1 || n == 2)
return 1;
return FibonacciRecursion(n - 1) + FibonacciRecursion(n - 2);
}
那么这个超级简单的递推程序，效率是多少呢？让我们加个数组，记录每次递归的次数，同时可以output一下，看看这些有趣的数字。
///<summary>
/// 递归输出Fibonacci
///</summary>
public ulong FibonacciRecursionCount(int n, int[] countArray)
{
countArray[n]++; //count the compute number.
if (n < 0)
throw new ArgumentOutOfRangeException("n must > 0.");
if (n == 1 || n == 2)
return 1;
return FibonacciRecursionCount(n - 1, countArray) + FibonacciRecursionCount(n - 2, countArray);
}
这时，可以得到每个fib(i)被计算的次数：
fib(10) = 1 fib(9) = 1 fib(8) = 2 fib(7) = 3
fib(6) = 5 fib(5) = 8 fib(4) = 13 fib(3) = 21
fib(2) = 34 fib(1) = 55 fib(0) = 34
可见，计算次数呈反向的Fibonacci数列，这显然造成了大量重复计算。
我们令T(N)为函数fib(n)的运行时间，当N>=2的时候我们分析可知：
T(N) = T(N-1) + T(N-2) + 2
而fib(n) = fib(n-1) + fib(n-2)，所以有T(N) >= fib(n)，归纳法证明可得：
fib(N) < (5/3)^N
当N>4时，fib（N）>= (3/2)^N
标准写法：