数据结构与算法数据结构与算法For For 软件学院软件学院0909级本科生级本科生 2010-2011 2010-2011秋秋3.1.5 3.1.5 栈与递归栈与递归栈与递归递归概念递归概念函数调用与递归实现函数调用与递归实现递归调用过程剖析递归调用过程剖析2递归定义在定义一个过程或函数时出现调用本过程在定义一个过程或函数时出现调用本过程或本函数的成分或本函数的成分, ,称之为递归。称之为递归。若调用自身若调用自身, ,称之为直接递归。称之为直接递归。若过程或函数若过程或函数p p调用过程或函数调用过程或函数q,q,而而q q又调又调用用p,p,称之为间接递归。称之为间接递归。 3递归定义常用来定义函数和数列。例如，阶乘函数！可以按照以下的方式定义：根据这一定义，可以产生数列： 1，1，2，6，24，120，720，5040，40320，362880，3628800， 其中包括了数0、1、2、10、的阶乘。 递归定义递归定义4另一个例子是下面的定义： 会产生有理数序列： 递归定义递归定义5序列的递归定义有一个不好的特性：为了确定序列中一个元素Sn的值，首先需要计算这个元素之前所有元素（S1、S2、Sn1）的值或其中一部分的值。例如计算3！的值需要首先计算0！、1！和2！的值。缺点：以迂回的方式进行计算。递归定义递归定义6等式比递归定义更可取，简化计算过程，不用计算第0、1、，n-1个元素的值，就可以计算第n个元素的值。例如，序列g定义为：可以转化成较简单的等式：递归定义递归定义7以下三种情况常常用到递归方法。1 定义是递归的2 数据结构是递归的3 问题的解法是递归的81 1 定义是递归的定义是递归的求解阶乘函数的递归算法求解阶乘函数的递归算法long Factorial ( long n ) if ( n = 0 ) return 1; else return n*Factorial (n-1);例如，阶乘函数例如，阶乘函数9求解阶乘求解阶乘 n! 的过程的过程10计算斐波那契数列的函数计算斐波那契数列的函数FibFib( (n n) )的定的定义义求解斐波那契数列的递归算法求解斐波那契数列的递归算法 long Fib ( long n ) if ( n = 1 ) return n; else return Fib (n- -1) + Fib (n- -2); 112 2 数据结构是递归的数据结构是递归的搜索链表最后一个结点并打印其数值搜索链表最后一个结点并打印其数值template void Find ( ListNode *f ) if ( f link = NULL ) cout f data endl; else Find ( f link ); 例如，单链表结构例如，单链表结构12template void Print ( ListNode *f, Type& x ) if ( f != NULL) if ( f -data = x ) cout -data - link, x );在链表中寻找等于给定值的结点并打印其数值在链表中寻找等于给定值的结点并打印其数值13 有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则：v每次只能移一个圆盘；v圆盘可在三个塔座上任意移动；v任何时刻，每个塔座上不能将大盘压到小盘上。3 3 问题解法是递归的问题解法是递归的Tower of Hanoi问题ABC14解决方法：n=1时，直接把圆盘从A移到C。n1时把上面n-1个圆盘从A移到B然后将n号盘从A移到C将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题。ABC15递归过程与递归工作栈递归过程与递归工作栈递归过程在实现时，需要自己调用自己。每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。层层向下递归，退出时的次序正好相反： 递归次序 n! (n-1)! (n-2)! 1! 0!=1 返回次序因此，每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。 16r主主程程序序srrrs子子过过程程1rst子子过过程程2rst子子过过程程317递归函数的实现递归函数的实现栈的一个最为广泛的应用对用户而言透明：程序运行环境所提供的函数调用机制运行时环境：目标计算机上用来管理存储器并保存执行过程所需的信息的寄存器及存储器的结构函数调用静态分配：（在非递归）数据区的分配可以在程序运行前进行，直到整个程序运行结束才释放。采用静态分配时，函数的调用和返回处理比较简单，不需要每次分配和释放被调函数的数据区动态分配：在递归调用的情况下，被调函数的局部变量不能静态地分配某些固定单元，而须每调用一次就分配一份，以存放当前所使用的数据，当返回时随即释放。故其存储分配只能在执行调用时才能进行：在内存中开辟一个称为运行栈（runtime stack）的足够大的动态区18函数运行时的动态存储分配函数运行时的动态存储分配用作动态数据分配的存储区可按多种方式组织。典型的组织是将这个存储器分为栈（stack）区域和堆（heap）区域栈区域用于分配发生在后进先出LIFO风格中的数据（诸如函数的调用）堆区域则用于不符合LIFO（诸如指针的分配）的动态分配19运行栈中的活动记录运行栈中的活动记录函数活动记录（activation record）是动态存储分配中一个重要的单元当调用或激活函数时，函数的活动记录包含了为其局部数据分配的存储空间 20运行栈中的活动记录运行栈中的活动记录运行栈随着程序执行时发生的调用链或生长或缩小每次调用一个函数时，执行进栈操作，把被调函数的活动信息压入栈中，即每个新的活动记录都分配在栈的顶部每次从函数返回时，执行出栈操作，释放本次的活动记录，恢复到上次调用所分配的数据区中被调函数中变量地址全部采用相对于栈顶的相对地址来表示一个函数在运行栈中可有若干不同的活动记录，每个代表一个不同的调用对于递归函数来说，递归的深度就决定了其在运行栈中活动记录的数目当函数递归调用时，函数体的同一个局部变量，在不同的递归层次被分配给不同的存储空间，放在内部栈的不同位置21函数调用与返回处理函数调用与返回处理调用可以分解成以下三步来实现：调用函数发送调用信息。调用信息包括调用方要传送给被调方的信息，诸如实参、返回地址等分配被调方需要的局部数据区，用来存放被调方定义的局部变量、形参变量（存放实参）、返回地址等，并接受调用方传送来的调用信息调用方暂停，把计算控制转到被调方，亦即自动转移到被调用的函数的程序入口当被调方结束运行，返回到调用方时，其返回处理一般也分三步进行：传送返回信息，包括被调方要传回给调用方的信息，诸如计算结果等释放分配给被调方的数据区按返回地址把控制转回调用方22递归时运行栈的变化示例递归时运行栈的变化示例以阶乘为例：以阶乘为例：#include main() int x;scanf(“%d”, &x)；printf(“%dn”, fact (4);23计算阶乘时的运行栈计算阶乘时的运行栈n: 4控制链返回地址第1次调用fact时的活动记录x: 4主程序main的活动记录栈生长方向栈生长方向n: 4控制链返回地址第1次调用factl时的活动记录x: 4主程序main的活动记录n: 3控制链返回地址第2次调用factl时的活动记录24计算阶乘时的运行栈计算阶乘时的运行栈栈生长方向n: 4控制链返回地址第1次调用fact 时的活动记录x: 4主程序main 的活动记录n: 3控制链返回地址第2次调用fact 时的活动记录n: 2控制链返回地址n: 1控制链返回地址第3次调用fact 时的活动记录第4次调用fact 时的活动记录自由空间1! = 12! = 2*1! = 23! = 3*2! = 64! = 4*3! = 2425递归算法的非递归实现递归算法的非递归实现以阶乘为例，非递归方式q建立迭代建立迭代q递归转换为非递归递归转换为非递归26计算阶乘计算阶乘n n！的循环迭代程序！的循环迭代程序 / 使用循环迭代方法，计算阶乘n!的程序long fact (long n) int m = 1;int i ;if (n 1)for ( i = 1; i 0) / ?s.push(n-);while (!isEmpty(s) / ?m *= s.pop(s);return m ; 29非递归程序的实现原理非递归程序的实现原理与递归函数的原理相同，只不过把由系统负责的保存工作信息变为由程序自己保存减少保存数据的冗余(主要是节省了局部变量的空间)，提高存储效率减少函数调用的处理以及冗余的重复计算，提高时间效率程序要完成的工作分成两类：手头工作 程序正在做的工作，必须有其结束条件，不能永远做下去保存在栈中的待完成的工作 由于某些工作不能一步完成，必须暂缓完成，把它保存在栈中，保存的待完成工作必须含有完成该项工作的所有必要信息。程序须有序地完成各项工作手头工作和待完成工作可互相切换待完成工作必须转换成手头工作才能处理30递归转换为非递归的方法递归转换为非递归的方法机械方法1.设置一工作栈保存当前工作记录2.设置 t+2个语句标号3.增加非递归入口4.替换第 i (i = 1, , t)个递归规则5.所有递归出口处增加语句：goto label t+1;6.标号为t+1的语句的格式7.改写循环和嵌套中的递归8.优化处理31设置一工作栈保存当前工作记录设置一工作栈保存当前工作记录在函数中出现的所有参数和局部变量都必须用栈中相应的数据成员代替返回语句标号域 (t+2个数值)函数参数(值参、引用型)局部变量 class elem / 栈数据元素类型int rd; / 返回语句的标号Datatypeofp1 p1; / 函数参数 Datatypeofpm pm;Datatypeofq1 q1; / 局部变量 Datatypeofqn qn; ;Stack S;32设置设置t+2t+2个语句标号个语句标号label 0 ：第一个可执行语句label t+1 ：设在函数体结束处label i (1=i=t)： 第i个递归返回处33增加非递归入口增加非递归入口/ 入栈elem tmp;tmp.rd = t+1; tmp.p1=p1; tmp.pm = pm;tmp.q1 = q1; tmp.qn = qn;S.push(tmp);34替换第替换第i (i=1,t)i (i=1,t)个递归规则个递归规则假设函数体中第i (i=1, , t)个递归调用语句为：recf(a1, a2, , am)；则用以下语句替换：S.push(i, a1, , am)； / 实参进栈goto label 0；.label i： x = S.pop()；/* 退栈，然后根据需要，将x中某些值赋给栈顶的工作记录S.top () 相当于把引用型参数的值回传给局部变量 */35所有递归出口处增加语句所有递归出口处增加语句 goto labelt+1;36标号为标号为t+1t+1的语句的语句switch (x=S.top ().rd) case 0 : goto label 0;break;case 1 : goto label 1;break;.case t+1 : item = S.pop()/ 返回处理break;default : break;37改写循环和嵌套中的递归改写循环和嵌套中的递归对于循环中的递归，改写成等价的goto型循环对于嵌套递归调用譬如，recf ( recf()改为：exmp1 = recf ( );exmp2 = recf (exmp1);exmpk = recf (exmpk-1)然后应用规则 4 解决38优化处理优化处理经过上述变换所得到的是一个带goto语句的非递归程序。可以进一步优化 去掉冗余进栈/出栈 根据流程图找出相应的循环结构，从而消去goto语句39递归的非递归实现递归的非递归实现请大家思考，用机械的转换方法2阶斐波那契函数f0=0, f1=1, fn = fn-1+ fn-2背包问题Hanio Tower40背包问题背包问题简化版：设有一背包可放入的物品重量为S，现有n件物品，重量分别为w0，w1， ，wn-1，问能否从这n件物品中选择若干件放入背包，使其重量之和正好为S。若存在一种符合上述要求的选择，则称此背包问题有解，否则无解。41背包问题背包问题bool knap(int s, int n) if (s = 0) return true;if (s 0 & n 1) return false; if (knap (s-wn-1, n-1) cout wn-1;return true; else return knap(s, n-1);42背包问题背包问题递归规则1.若wn-1包含在解中，求解knap(s-wn-1, n-1)2.若wn-1不包含在解中，求解knap(s, n-1)+ 递归出口，共有3种返回地址：1.计算knap(s, n)完毕返回调用它的函数；2.计算knap(s-wn-1, n-1)完毕，返回到本调用函数继续计算；3.计算knap(s, n-1)完毕，返回到本调用函数继续计算。43背包问题背包问题转换如下：1凡调用语句knap(s, n)均代换成 (1) tmp.s = s; tmp.n = n; tmp.rd = 返回地址编号 (2) stack.push(tmp); (3) 转向递归入口2将调用出口的返回处理统一： (1) stack.pop(&tmp); (2) 分以下情况执行 i) tmp.rd = 0 时，算法结束 ii) tmp.rd = 1时，转规则1返回处理 iii) tmp.rd = 2时，转规则2返回处理44