|
栈与递归 () 递归 所谓 递归 是指若在一个函数过程或者数据结构定义的内部直接(或间接)出现定义本身的应用则称它们是递归的或 者是递归定义的 递归是一种强有力的数学工具它可使问题的描述和求解变得简洁和清晰 递归算法常常比非递归算法更易设计尤其是当问题本身或所涉及的数据结构是递归定义的时候使用递归算法特别合适 ()递归算法的设计步骤 第一步骤(递归步骤) 将规模较大的原问题分解为一个或多个规模更小但具有类似于原问题特性的子问题即较大的问题递 归地用较小的子问题来描述解原问题的方法同样可用来解这些子问题 第二步骤 确定一个或多个无须分解可直接求解的最小子问题(称为 递归的终止条件 ) 【例】非负整数n的阶乘可递归定义为 ()栈在递归算法的内部实现中所起的作用 ①调用函数时系统将会为调用者构造一个由参数表和返回地址组成的活动记录并将其压入到由系统提供的运行时刻栈的栈 顶然后将程序的控制权转移到被调函数若被调函数有局部变量则在运行时刻栈的栈顶也要为其分配相应的空间因此活动记 录和这些局部变量形成了一个可供被调函数使用的活动结构 注意 参数表的内容为实参返回地址是函数调用语句的下一指令的位置 ②被调函数执行完毕时系统将运行时刻栈栈顶的活动结构退栈并根据退栈的活动结构中所保存的返回地址将程序的控制权 转移给调用者继续执行 【例】Factorial()递归函数执行期间运行时刻栈的变化(不考虑局部变量temp的入出栈情况) |
