第3章 递归算法.ppt

第3章递归算法,递归算法概述,递归是一种强有力的设计方法递归算法的特点简单明了易于证明递归的效率问题,递归算法的基本思想将求解某个较大的问题转化成若干个较小的问题，反复的进行转化直到问题小到可以直接求解，若这些较小的问题与较大的问题性质相同，则递归调用同样的算法进行求解。递归的条件（1）递归的下一步比上一步要简单；（2）在有限步内完成；（3）必须有递归出口。,3.1递归算法的实现机制3.1.1子程序的内部实现原理1.子程序调用的一般形式,当主程序执行到CallA时，系统自动保存好1的地址，便于调用A结束后能从系统获得返回地址。,主程序中有多次对同一程序A的调用。在第i次重复调用子程序A之前，系统自动的保存好地址i，便于第i次调用A结束后能顺利地按地址i返回。这种情况与1次调用不同，需要保存的地址有多个，但在某一时刻最多只有一个地址，一旦获得地址后后，保留地址被被释放。,主程序,子程序A,CallA1:CallA2:,n次调用,主程序,子程序A,子程序B,CallB2:,CallA1:,嵌套调用,主程序,子程序A,子程序B,CallB1:,CallA2:,平行调用,对于上述两种情况当主程序执行到CallA或CallB时，系统自动地保存好地址1，在第二次调用子程序CallB或CallA时，再保存好地址2。这两种情况与前面两种情况不同，在某一时刻可能保存多个地址，而且后保存的地址先释放。这里的返回地址我们通常用栈这种数据结构来保存。,栈在过程调用中的作用：在过程调用中我们需要将实参的值带给形参，需要将过程的返回地址临时存放在某处，在过程中还需要分配一些局部变量，这些数据通常我们将其存放在堆栈中。2.值的回传实参与形参的数据传输方式：一、按值传送（比如：C语言中的参数传递方式，以及在PASCAL中的值参）调用前后值参对应的实参不发生变化二、按地址传送（比如PASCAL中的变参）变参对应的实参的值将执行过程中对变参的修改进行回传。对于变参回传值，有两种实现方式：,（1）两次值传方式。按指定类型为变参设置相应的存储空间，在执行调用时，将实参传送给变参，在返回时将变参的值回传给实参。（2）地址传送方式。在内部将变参设置一个地址，调用时首先执行地址传送，将实参的地址传送给变参，在子程序执行过程中，对变参的操作实际上变成对对应的实参的操作。在后面的讨论中，对变参的值的回传用第一种方式，即两次值传送方式。,3.子程序调用的内部操作（1）在执行调用时，系统执行的操作：a.返回地址进栈，同时在栈顶为被调子程序的局部变量开辟空间；b.为被调子程序准备数据：计算实参值，并赋给对应的栈顶的形参；c.将指令流转入被调子程序的入口处。（2）在执行返回操作时，系统执行的操作：a.若有变参或是函数，将其值保存到回传变量中；b.从栈顶取出返回地址；c.按返回地址返回；d.若有变参或是函数，从回传变量中取出保存的值传送给相应的变量或位置上。,Proceduremain()ProcedureA(x1,x2)endAProcedureB(x3,x4)callA(e,f)3:endBcallA(a,b)1:callB(c,d)2:endmain,1,a,b,3,e,f,c,d,2,堆栈,3.1.2递归过程的内部实现原理递归调用过程被看作是嵌套调用自身的过程，其调用和返回的原理与子程序的调用和返回相同。需要注意的是在递归调用自身时，并不是将自身代码进行复制，然后执行复制代码，而是采用代码共享的方式，即程序控制跳转到同一段代码执行，不同的是当前堆栈中对应的形参和局部变量的数据不同。,例1.3斐波那契(Fibonacci)序列：F0=F1=1Fi=Fi-1+Fi-2（i1)算法1.7求斐波那契数列procedureF(n)/返回第n个斐波那契数/integernifnb/ifb=0thenreturn(a)elsereturn(GCD(b,amodb)endifendGDC例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;,例1.5用递归策略设计的检索算法已知元素x和元素表A（1：n），判断x是否等于A中某元素的值。算法1.9在A（1：n）中检索xprocedureSEARCH(i)/如果在A（1：n）中有一元素A（k）=x，则将其第一次出现的下标k返回，否则返回0/globaln,x,A(1:n)case:in:return(0):A(i)=x;return(i):else:return(SEARCH(i+1)endcaseendSEARCH,3.2递归转非递归,直接递归的消去规则：基本思路：将递归调用的地方用等价的非递归代码来代替，并对return语句做适当处理。13条规则：处理直接递归调用和return语句，将之转换成等价的迭代代码。初始化在过程的开始部分，插入说明为栈的代码并将其初始化为空：StackTypeStack1.SIZETop0在一般情况下，这个栈用来存放参数、局部变量和函数的值、每次递归调用的返回地址。,将标号L1附于第一条可执行语句。L1：第一条可执行语句然后对于每一处递归调用都用一组执行下列规则的指令来代替。,处理递归调用语句将所有参数和局部变量的值存入栈。TopTop+1StackTop栈顶指针可作为一个全程变量来看待。建立第i个新标号Li，并将标号的下标i存入栈。这个标号的i值将用来计算返回地址。TopTop+1StackTopi此标号放在规则所描述的程序段中。,保存现场,计算这次调用的各实在参数（可能是表达式）的值，并把这些值赋给相应的形式参数。插入一条无条件转向语句转向过程的开始部分：gotoL1(以上完成一次递归调用),对退出点的处理如果这过程是函数，则对递归过程中含有此次函数调用的那条语句做如下处理：将该语句的此次函数调用部分用从栈顶取回该函数值的代码来代替，其余部分的代码按原描述方式照抄，并将中建立的标号附于这条语句上。,如果此过程不是函数，则将中建立的标号附于所产生的转移语句后面的那条语句。,以上步骤消去过程中的递归调用。下面对过程中出现return语句进行处理。注：纯过程结束处的end可看成是一条没有值与之联系的return语句,对每个有return语句的地方，执行下述规则：如果栈为空，则执行正常返回。iftop0thenreturn()否则，将所有输出参数（带有返回值的出口参数，out/inout型）的当前值赋给栈顶上的那些对应的变量。Stackn,如果栈中有返回地址标号的下标，就插入一条此下标从栈中退出的代码，并把这个下标赋给一个未使用的变量。addrStackTopTopTop-1从栈中退出所有局部变量和参数的值并把它们赋给对应的变量。,如果这个过程是函数，则插入以下指令，这些指令用来计算紧接在return后面的表达式并将结果值存入栈顶。TopTop+1StackTop表达式的值用返回地址标号的下标实现对该标号的转向。ifaddrithengotoLi,例1.6递归调用示例求数组元素中的最大值算法1.10求取数组元素的最大值（递归算法）procedureMAX1(i)/查找数组A中最大值元素，并返回该元素的最大下标。/globalintegern,A(1:n),j,kintegeriifiA(j)thenkielsekjendifelseknendifreturn(k)/递归调用的返回/endMAX1,max(a1,an)=max(a1,max(a2,an),消去上例中的递归算法1.11使用上述的规则消去例1.10中的递归代码procedureMAX2(i)localintegerj,k;globalintegern,A(1:n)integeriintegerSTACK(1:2*n)top0/规则1，声明栈的代码，并初始化为空/L1:ifiA(j)thenkIelsekjendifelseknendif,iftop=0thenreturn(k)/规则8，如果栈空，则正常返回/elseaddrSTACK(top);toptop-1;/规则10，从栈中退出返回标号/iSTACK(top);toptop-1;/规则11，从栈中退出局部变量和参数的值/toptop+1;STACK(top)k;/规则12，计算返回值，并将之入栈/ifaddr=2thengotoL2endif/规则13，用返回地址标号的下标实现对该标号的转向/endifendMAX2,进一步优化和简化经过消去递归产生的迭代程序。,算法1.12算法1.11的改进模型procedureMAX3(A,n)integeri,k,n;iknwhilei1doii-1ifA(i)A(k)thenkiendifrepeatreturn(k)endMAX3,3.3递归算法设计递归求解需要考虑的问题：（1）问题P的描述涉及规模，即P(size)；（2）规模发生变化后，问题的性质不发生变化；（3）问题的解决有出口。递归算法的一般形式：procedureP(参数表)if递归出口then简单操作elsebegin简单操作;callP;简单操作endendifendP,例3.30/1背包问题设已背包可容物品的最大质量为m，现有n件物品，质量为m1,m2,mn,mi,均为正整数，要从n件物品中挑选若干件，使放入背包的质量之和正好为m。在0/1背包问题中，第i件物品要么取，要么舍。于是我们可以用一个布尔函数来表示这个问题。我们用knap(m,n)来表示n件物品放在背包中背包中的物品的质量之和为m的布尔函数。（1）先取最后一件物品mn放入包中，若mn=m，则knap0。如果还有可选物品，即n1，就变为考虑knap(m-mn,n-1)是否可行的问题，也就是当选中的是mn时，看子问题knap(m-mn,n-1)是否有解。如果有解，则knap(m,n)转化为knap(m-mn,n-1)否则knap(m,n)转化为knap(m,n-1)即放弃mn,在m1,mn-1上考虑0/1背包问题。,booleanprocedureknap(m,n)casem-mn:=0:knap0:beginifn1thenifknap(m-mn,n-1)=truethenknap(9,10)第二步0001011_1(8,9)-(4,5)第三步0_1011001(2,3)-(8,9)第四步010101_01(7,8)-(2,3)第五步_01010101(1,2)-(7,8)n=50000011111_第一步0000_111101(5,6)-(11,12)第二步00001111_01(9,10)-(5,6)对于n=5的情况可以按照上面两步将前面的棋子转换成n=4的情况进行求解。,递归过程如下：procedurechess(n)ifn=4thenmove(4,5)-(9,10)move(8,9)-(4,5)move(2,3)-(8,9)move(7,8)-(2,3)move(1,2)-(7,8)elsemove(n,n+1)-(2n+1,2n+2)move(2n-1,2n)-(n,n+1)callchess(n-1)endifendchess,例3.6求n个元素的全排列分析n=3的情况，可以将全排列分成如下3类：(1)a1类：a1之后跟a2,a3的所有全排列(2)a2类：a2之后跟a1,a3的所有全排列(3)a3类：a3之后跟a2,a1的所有全排列将(1)中a1,a2的互换位置，得到(2)；将(1)中a1,a3的互换位置，得到(3)。它说明可以用循环的方式重复执行交换位置，后面跟随剩余序列的所有排列，对剩余序列再使用这个方法，这就是递归调用，当后跟的元素没有时就是递归的边界。于是n个元素的全排列算法如下：,procedurerange(a,k,n)ifk=nthenprint(a)elseforiaicallrange(a,k+1,n)endendp；在主程序中的调用是callrange(a,1,n),例3.7自然数拆分任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和，试求n的所有拆分。例如：n=2可以拆分成2=1+1n=3可以拆分成3=1+2=1+1+1n=4可以拆分成4=1+3=1+1+2=1+1+1+1=2+2n=5可以拆分成5=1+4=1+1+3=1+1+1+2=1+1+1+1+1=2+3=2+2+1,用数字a存储完成n的一种拆分。从上面不完全归纳法可知按照a1分类有a1=1,a1=2,a1=3,a1=n/2，共n/2大类拆分。在每一类拆分时令a1-i，a2-n-i，从k=2，继续拆分从ak开始，ak能否再拆分取决于ak/2是否大于等于ak-1。因此可以有如下拆分算法proceduresplit(t:int)/t指向要拆分的数ak/fork-1totdowrite(ak);j-t;L-aj;fori-aj-1toL/2doaj-i;aj+1-L-i;callsplit(j+1);repeatendpproceduremain(n)fori-1ton/2doa1-i;a2-n-i;callsplit(2);repeatendmain,递归算法时间复杂度分析递归算法的时间复杂度可以通过建立算法时间复杂度的递归关系式，然后求得算法的时间复杂度。例3.8在前面求数组A(1:n)的最大元问题这里采用自然语言描述此算法。解：procedureMax(i,j)/这是一个函数过程，它将A(i:j)中的最大元赋予Max(i,j)/(1)当j-i2时，采用逐一比较的方法求出A(i:j)的最大元，并给Max(i,j)赋相应值;(2)当j-i2时L-|(i+j)/2|若Max(i,L)Max(L+1,j)则Max(i,j)-Max(i,L)否则M(i,j)-M(L+1,j),下面对算法的时间复杂度进行分析：设算法的时间复杂