Question

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

Answer 1

　　 栈与递归

　　( ) 递归

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

　　者是递归定义的

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

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

　　( )递归算法的设计步骤

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

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

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

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

　　

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

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

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

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

　　注意

　　

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

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

　　转移给调用者继续执行

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

lishixinzhi/Article/program/sjjg/201311/23918