扫码获取更多资源

●栈与递归问题

栈还有一个重要应用是在程序设计语言中实现递归。一个直接调用自己或通过一系列 的调用语句间接地调用自己的函数，称为递归函数。

递归是程序设计中一种强有力的数学工具，它可以使问题的描述和求解变得简洁和清 晰。递归算法常常比非递归算法更易设计，尤其是当问题本身或所涉及的数据结构是递归 定义的时候，使用递归算法特别合适。例如：

(1)有很多数学函数是递归定义的，如非负整数的阶乘函数；

(2)有的数据结构，如二叉树、广义表等，由于结构本身固有的递归特性，使得它们的操 作可以递归地描述；

(3)还有一类问题，虽然问题本身没有明显的递归结构，但用递归求解比迭代求解更简 单，如八皇后问题、汉诺(Hanoi)塔问题等。

※递归算法的设计

(1)递归基本步骤：将规模较大的原问题分解为一个或多个规模更小、但具有类似于 原问题特性的子问题。即较大的问题递归地用较小的子问题来描述，解原问题的方法同样 可以用来解这些子问题。

(2)递归终止条件：确定一个或多个无须分解、可直接求解的最小子问题。

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

多个函数的嵌套调用。当在一个函数的运行期间调用另一个函数时，调用前系统需要先完成三件事情：

(1)所有实参、返回地址等信息传递给被调用函数保存；

(2)为被调用函数的局部变量分配存储区；

(3)将控制权转移到被调用函数的入口。

调用后，系统也应该完成三件事情：

(1)保存被调用函数的计算结果；

(2)释放被调用函数数据区；

(3)依照被调用函数保存的返回地址将控制权转移到调用函数。

当有多个函数构成嵌套调用时，按照“后调用先返回”的原则，函数之间的信息传递和控 制必须通过“栈”来实现，即系统将整个程序运行时所需要的数据空间都安排在一个栈中： 每当调用一个函数时，就为它在栈顶分配一个存储区；每当从一个函数退出时，就释放它的 存储区。因此当前运行的函数的数据域必在栈顶。 递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数，因此和每 次调用相关的一个重要概念是递归函数运行的“层次”。假设调用该递归函数的主函数 为第。层，则从主函数调用递归函数就为第1层；从第i层递归调用本函数为进入“下一 层”，即第i+1层。反之，退出第i层递归应该返回至“上一层”，即第1—1层。为了保证 递归函数正确执行，系统需要设立一个“递归工作栈”作为整个递归函数运行期间使用的 数据存储区。每一层递归所需要的信息构成一个“工作记录”，其中包括所有实参、局部 变量及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶；每退 出一层递归，就从栈顶弹出一个工作记录，则当前执行层的工作记录必是递归工作栈栈 顶的工作记录。

联系我们：