斐波那契数列，又称黄金分割数列，是指这样一个数列：0、1、1、2、3、5、8、13、21、34......特别指出：第0项是0，第1项是第一个1。
斐波那契数列的发现和研究源于哥德尔、艾舍尔、巴赫（GEB）这本书。我们来说说这个有趣的数列。
首先我们从一个兔子问题开始：如果有一对兔子，从出生后第三个月起每个月都生一对兔子，新生的一对兔子从出生后第三个月后又每个月生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？
我们把这个问题先放在一边，另先看另一个问题：一个人在第n个月完全靠将父母赠送的100元钱生活。他从第一个月开始行动，他的生活费用每个月都是前一个月的生活费用的倍数。即第一个月100元，第二个月200元（100元的两倍），第三个月400元（200元的两倍）......依次类推。假如这个人可以靠这笔钱一直生活下去，那么他在第几个月会跨进第一桶金（即累计生活费支出达到10万元）呢？
上面两个问题看似毫不相关，但是，有趣的是答案是完全相同的。
【图片】
看到图片中那个一块块的蜂窝状东西了么？就是斐波那契数列的一个良好应用吧。现在开始从问题本身来解释斐波那契数列，这是一个非常优美、简洁、神奇数列，常常出现在自然界中。
讲得简单一点：斐波那契数列是这样一个数列0、1、1、2、3、5、8、13、21、34......在这个数列中每一个数是该数前面两个数的和。
那我们来看看和兔子问题之间的联系吧。我们假设在n个月时有F(n)对兔子，由前提可知它以以下递归方式生成——第一个月有一对兔子，从第三个月起每个月都有新出生的兔子加入，因此第n个月的兔子总数为它前两个月的总兔子数之和。换句话说，F(n)=F(n-1) F(n-2)。我们把F(0)=0、F(1)=1置于不等式起始处，得到如下不等式：
F(0)＝0F(1)＝1F(2)＝F(1) F(0)＝1F(3)＝F(2) F(1)＝2F(4)＝F(3) F(2)＝3F(5)＝F(4) F(3)＝5F(6)＝F(5) F(4)＝8......
我们结合斐波那契数列的公式和这个不等式，可以将此问题简单地表述如下：若F(n)代表第n个月的兔子对数，那么有：F(n)=F(n-1) F(n-2)（n>=2，n∈N*）。
是不是看起来有些复杂呢？不用担心，理解数据结构的小伙伴应该都知道算法分析中的时间与空间复杂度。经过分析，我们可以得到如下公式用于求解：
- 时间复杂度：O（2^n）
- 空间复杂度：O（1）
以上公式对程序员来说可能意义更大一些，对其他人来说，只需要知道斐波那契数列是如此优美、巧妙和神奇就可以了。所以，当下一次和朋友聊天，看到依次递增的数字时，请大声地说出：“这是斐波那契数列，你知道它的由来吗？很有趣哦！”
