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

导言 本文假定阅读者已具备“递归思想”的基本知识，并具有用递归程序解决简单问题的能力和经验。在此基础上，本文将以斐波那契数列问题的求解作为例子，简单阐述递归的四项基本法则，给出此程序时间复杂度的数学证明，并最终优化斐波那契数列的算法。 回顾递归思想 我们熟悉的数学函数通常是由一个确定的公式描述的。与之不同的是，递归函数通过调用它自身来完成定义。这就是说，在函数的定义体内部存在函数本身。例如，