前置文章：递归算法：www.jianshu.com/p/703069f3ba3f .
虽然我说递归算法算得上是一种底层的算法，但是递归算法的应用很广泛的。
递归算法的一个经典应用是Fibonacci数列（斐波那契数列），我为数不多的非常喜欢的一个数列。Fibonacci数列的定义是这么说的：斐波那契数列的每一项都等于前两项之和（明显第一项和第二项是特殊项）。
斐波那契的概念非常容易理解。打个比方，我现在手里有一片苹果林，我这苹果林每年都会生产很多的苹果，我拿这苹果干嘛呢，我这苹果不吃，我也不卖，我用来喂兔子，我养兔子。我养这兔子跟吃苹果不一样，我这兔子第一年出生，然后长一年，第二年开始能进行生殖，一年一次，一次一窝，一窝一个。
我从邻居换来的兔一
我今年就抱着一堆苹果去我邻居那换了个兔崽子，我还给它起了个名，叫兔一，第一年我有一只兔子。 F(1) = 1.
兔一今年长一年，然后第二年，兔一生了一个兔子，我叫它兔二，第二年我有俩兔子，成熟得兔一和还是崽子的兔二。 F(2) = 2.
第三年，兔一生一个兔子，叫兔三，兔二长大成兔，我这第三年就有了三只兔子，兔一二三。 F(3) =F(1)+F(2) = 1+2 = 3.
第四年，兔一、兔二都生了一只，叫兔四、兔五，然后兔三长大了。说到这，有种葫芦娃的感觉是吧，我这兔老大、老二、老三都有了，然后一下出来了兔四五。然后这兔子现在又多了，我现在五只兔子。 F(4) = F(2) + F(3) = 2+3 = 5.
第五年，兔一二三都开始生兔子了，然后兔四五长大了，我又多了三只兔子，兔六七八。我现在有了八只兔子了。F(5) = F(4) + F(3) = 5+3 = 8.
第六年，我这兔子就非常可观了，我有8+5=13只兔子。说到这里，已经非常明白了，我这里兔子是一年熟，然后开始生殖的，也就是隔年生。那我今年拥有的兔子就是我去年有的兔子和我前一年有的兔子之和，因为前年的兔子不管大小，今年一定能生，生下来的就是净增长。所以，我这兔子就能推出一个公式：F(n) = F(n-1)+ F(n-2) (n>=2).
我这养兔子的过程就是一个典型的斐波那契数列的问题，一个递推的问题，这个题目也是斐波那契数列的典型应用。而递归要求的基准情形，也就是递归出口：我兔子养的太多了，我苹果不够了，那我就不继续养兔子，我可能是把它们卖了，或者是送人，那这个递归就结束了。
用兔子来讲斐波那契数列非常清晰明了了。斐波那契数列的递推算法也就有了：
int fib[50];
void fibonacci(int n) {
fib[0] = 1;
fib[1] = 1;
for( int i=2; i<=n; i++){
fib[i] = fib[i-1] + fib[i-2];
}
}
我说我很喜欢斐波那契数列，不仅仅是因为斐波那契数列在算法应用上简单并且实用性广，而是因为，斐波那契数列的美，数学美，艺术美：
斐波那契数列的数学美是美在：数列中的每前后两项做的比值，也就是F(n-1)/F(n) ，随着斐波那契数列数值的增长，比值趋近于黄金分割线，也就是0.618。而斐波那契数列的艺术美是美在：
斐波那契螺旋线
斐波那契螺旋曲线！！！多么令人惊艳的数学图形。
完美的斐波那契，真正的演算公式或者算法公式却仅仅用几行文字就能表达出来，如我所说：
网友评论