栈的应用之递归，以斐波那契数列为例

栈的应用——递归

在讨论栈的应用之前，先来看看栈的作用，用数组和链表直接实现功能不就行了吗，为啥还需要引入栈呢，哈。人明明有腿脚，又能走又能跑，干嘛还有乘坐交通工具呢。其实栈的引入简化了程序设计的问题，划分了不同的关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。反之，像数组等，因为要分散精力去考虑数组的下标增减等细节问题，反而掩盖了问题的本质。所以现在许多高级语言，如 Java、c# 等都有对栈结构的封装，使得我们可以不用关注它的实现细节，就可以直接使用 Stack 的 push 和 pop 方法，非常方便。

栈有一个很重要的应用：在程序设计语言中实现了递归。那什么是递归呢？

早上起来。当以往镜子面前一站，镜子里面就有一个你的像，如果再拿一面镜子，使两面镜子 A、B面对面放着，你往中间一站，两面镜子里有许多个你的影子。原因就是，镜子里有B镜子的像，B镜子里也有A镜子的像，这样反反复复，就会产生一连串的“像中像”。这是一种递归现象，如图：

斐波那契数列实现

一个经典的递归例子：斐波那契数列(Fibonacci)。为了说明这个问题，这位数学家还列举了这样一个例子：说如果兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出来一对小兔子来。假设所有兔子不死，那么一年后可以繁殖多少对兔子呢？

我们拿新出生的一对小兔子分析一下：第一个月小兔子没有繁殖能力，所以还是一对；两个月后，生下一对小兔子数共有两对；三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对……依次类推可以列出下表：

表中数字1，1，2，3，5，8，13……构成了一个序列。这个数列有个十分明显的特点，那是：前面相邻两项之和，构成了后一项，如图：

可以发现，编号①的一对兔子经过六个月就变成8对兔子了。如果我们用数学函数来定义就是