chapt栈和队列栈二.pptVIP

1.1.4 递归的执行过程—函数调用、信息传递 1. 普通函数的调用过程 在高级语言编制的程序中，调用函数和被调函数之间的链接和信息交换需要通过堆栈来进行。 系统将整个程序运行所需的数据空间安排在一个堆栈中。 通常，在一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统先要完成三件事：1、将所有的实参、返回地址等信息传递给被调函数保存；2、为被调函数的局部变量分配存储区；3、将控制转移到被调函数的入口。 当执行完被调函数，在返回调用函数之前，系统也先要完成三件事：1、保存被调函数的计算结果；2、释放被调函数的数据区；3、依照被调函数保存的返回地址将控制转移到调用函数。 当有多个函数构成嵌套调用时，按照“后调用先返回”的原则，函数之间的信息传递和控制转移均通过堆栈来实现。 每当调用一个函数时，就在堆栈顶端为它分配一个存储区，保存其参数（实参、局部变量）和返回地址等信息；每当从一个函数退出时，就释放它的存储区，使得当前正在运行函数的数据区总是在栈顶。 最后被调用的函数，其相关的参数和返回地址等信息作为栈顶元素，我们称之为栈顶工作记录，因为是当前执行函数的工作记录，也称之为“活动记录”。指向活动记录的指针通常也被称为“环境指针。” 【例3.6】两个子函数first、second的嵌套调用 int first(int a, int b) { int i; …… second(i); 2：…… } int second(int d); { int x,y; …… } 当前运行函数为second时，堆栈状态如右上图所示。工作记录的内容：返回地址（被调函数的下一语句，控制转移至调用函数）、实参、局部变量。 执行完最后调用的函数second后，栈顶记录被pop出去，控制转移至返回地址‘2’，接着执行first函数的其它语句。 执行完first函数语句，当前栈顶记录（first的记录）又被pop出去，控制转移至返回主函数地址‘1’，接着执行主函数中的其它语句。 2. 递归函数的调用过程 一个递归函数的嵌套过程类似于多个函数的嵌套调用。只是调用函数和被调函数均为同一个函数。唯一的不同点是其中的一个传入参数每次执行函数调用时都递减（增）。 这个传入参数可以表明递归函数运行的“层次”。 若调用递归函数的主函数为第0层，那么从主函数调用递归函数为进入第一层。从第i 层递归函数调用自身为进入第i+1层。反之，第i层函数执行完退回至i-1层。 系统也需要设立一个“递归工作栈”作为整个递归函数运行期间使用的数据区，不需用户自己管理，而由系统完成管理工作。 每一层递归函数所需信息也构成一个“工作记录”。最“高”层的工作记录就是栈顶的活动记录。指示活动记录的栈顶指针为“当前环境指针”。 【例3.7】设计一个乘法器（只能做加法） 分析：A*B=A+(A*(B－1))= A+A+(A*(B－2))=A+A+……+A*1 B个A B=1为循环结束的条件（递归结束） 运算规律：每次运算时，A所乘的数B依次递减，将所乘的积返回再与A相加。 算法如下页。 主函数定义了一个乘积变量product。实参A、B；形参M、N；局部变量result。result返回运算值给product。 主函数对递归函数的调用：product=multiply(NumA, NumB) 递归体：result = M+ multiply(M, N-1) 乘法器算法如下： int Multiply(int M, int N) { int Result; if (N==1) Result=M; else Result=M+Multiply( M, N-1); 20 return Result; } 表述乘法器算法的递归工作栈如下： 栈顶记录 M 第4层 20; A ,B ; Result Multiply(13,1)