栈和队列 - 栈和队列的应用实例 - 栈的应用实例（二）

栈与递归

( ) 递归

所谓 递归 是指 若在一个函数 过程或者数据结构定义的内部 直接(或间接)出现定义本身的应用 则称它们是递归的 或

者是递归定义的

递归是一种强有力的数学工具 它可使问题的销孝衫描述和求解变得简洁和清晰

递归算法常常比非递归算法更易设计 尤慎棚其是当问题本身或所涉及的数据结构是递归定义的时候 使用递归算法特别合适

( )递归算法的设计步骤

第一步骤(递归步骤) 将规模较大的原问题分解为一个或多个规模更小 但具有类似于原问题特性的子问题 即较大的问题递

归地用较小的子问题来描述 解原问题的方法同样可用来亏腔解这些子问题

第二步骤 确定一个或多个无须分解 可直接求解的最小子问题(称为 递归的终止条件 )

【例】非负整数n的阶乘可递归定义为

( )栈在递归算法的内部实现中所起的作用

①调用函数时 系统将会为调用者构造一个由参数表和返回地址组成的活动记录 并将其压入到由系统提供的运行时刻栈的栈

顶 然后将程序的控制权转移到被调函数 若被调函数有局部变量 则在运行时刻栈的栈顶也要为其分配相应的空间 因此 活动记

录和这些局部变量形成了一个可供被调函数使用的活动结构

注意

参数表的内容为实参 返回地址是函数调用语句的下一指令的位置

②被调函数执行完毕时 系统将运行时刻栈栈顶的活动结构退栈 并根据退栈的活动结构中所保存的返回地址将程序的控制权

转移给调用者继续执行

【例】Factorial( )递归函数执行期间运行时刻栈的变化(不考虑局部变量temp的入出栈情况)

lishixinzhi/Article/program/sjjg/201311/23918

栈：铁路调度中用到栈。

队列：民航机票订购。

栈作为一种数据结构，是一种只能在一端进行插入和删除数尺 *** 作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底。

最后的数据在栈顶，需要读数据的时候从栈顶开始d出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除 *** 作中，不需要改变栈底指针。

扩展资料：

由于入队和出队 *** 作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队 *** 作。

在循环队列中，当队列为空时，有front=rear，而当所有敏做队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列桥毕衡就已经满了。

---