搜索
数据结构递归算法递归算法(Recursion)本章内容递归算法定义递归算法举例递归算法复杂性的计算递归算法数据结构递归算法递归(Recursion)定义直接或间接地调用自身的算法称为递归算法直接或间接调用自身的函数称为递归函数尾递归是指递归调用的语句在递归函数的最后一句递归算法的特点：用于解决一类递归定义的问题算法易于实现，简单明了递归算法数据结构递归算法递归算法：1(n=0,1)n!=n(n-1)！(n1)数据结构递归算法函数的递归调用1.定义：在调用一个函数的过程中直接或间接地调用该函数本身。直接调用intf(x)intx;{inty,z;…..z=f(x);……return(2*z);}f函数调用f函数数据结构递归算法intf1(x)intx;{inty,z;…..z=f2(y);……return(2*z);}intf2(t)intt;{inta,c;…..c=f1(a);……return(3+c);}•间接调用数据结构递归算法特点是无终止的递归调用，因此，应该给定一个限制递归次数的条件。f1函数调用f2函数f2函数调用f1函数数据结构递归算法floatfac(intn){floatf;if(n0)printf(“n0,dataerror!\n”);elseif(n==0||n==1)f=1;elsef=fac(n-1)*n;returnf;}例如：写一函数求n!数据结构递归算法以求4的阶乘为例：fac(4)=4*fac(3)fac(3)=3*fac(2)fac(2)=2*fac(1)fac(1)=1fac(4)=4*3*2*1fac(2)=2*1fac(3)=3*2*1下推回代数据结构递归算法利用栈实现递归调用主程序(1)输出f(4);……4f(4);（1）n=4top(2)s=4*f(3)n3f(3);（2）n=3（1）n=4top(3)s=3*f(2)n2f(2);（3）n=2（2）n=3（1）n=4top(4)s=2*f(1)n1（4）n=1（3）n=2（2）n=3（1）n=4topss=3*2*1;(2)3(1)4tops=2*1(3)2(2)3(1)4tops=4*3*2*1(1)4top返回(3)2(2)3(1)4top(4)1结束输出24数据结构递归算法使用递归的准则如果待解决的问题具备下列两个特性，就可以考虑使用递归。1)复杂的问题可以转换为简单些的1个或几个子问题；2)最简单的问题可以直接解决数据结构递归算法例1.3斐波那契(Fibonacci)序列：F0=F1=1Fi=Fi-1+Fi-2（i1)算法求斐波那契数procedureF(n)//返回第n个斐波那契数//integernifn≤1thenreturn(1)elsereturn(F(n-1)+F(n-2))endifendF算法效率：对F(n-1)、F(n-2)存在大量的重复计算，可以改进算法：保存中间结果数据结构递归算法例1.4欧几里得算法已知两个非负整数a和b，且a＞b≥0，求这两个数的最大公因数。辗转相除法：若b=0，则a和b的最大公因数等于a；若b＞0，则a和b的最大公因数等于b和用b除a的余数的最大公因数。算法1.8求最大公因数procedureGCD(a,b)//约定ab//ifb=0thenreturn(a)elsereturn(GCD(b,amodb))endifendGCD例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;数据结构递归算法例1.5递归在非数值算法设计中的应用已知元素x，判断x是否在A（1：n）中。算法在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数据结构递归算法子程序的调用形式递归算法的实现机制主程序CallA1:……子程序A一次调用主程序CallA1:……CallA2:……子程序A多次调用…1STACK…1/2STACK数据结构递归算法主程序CallA1:……子程序ACallB2:…子程序B嵌套调用子程序A主程序CallB1:……子程序BCallA2:…平行调用递归算法的实现机制…12STACK…12STACK数据结构递归算法2.递归算法设计定义递归（数学公式，数列等的定义。）数据结构递归（单链表，树，二叉树）可用递归解决的问题P（hanoi问题）问题P具有大规模不同规模的问题P，具有相同性质；并且大规模的问题由小规模的问题构成小规模的问题是可解的关键：找到递归的递推关系找到结束递归的条件3.递归算法设计数据结构递归算法递归求解的伪代码procedureP(参数表)beginif满足递归出口then简单操作elsebegin简单操作;CALLP;简单操作;end;endendp3.递归算法设计数据结构递归算法简单的0/1背包问题设一个背包容纳的物品最大质量为m,现有n件物品，质量为m1,m2,…,mn,均为正整数。要求从中挑选若干件，使背包质量之和正好为m.（在此问题中，第i件物品要么取，要么不取，不能取一部分，故问题可能有解，可能无解）设用knap(m,n)来表示此问题。有解为true,否则为false3.递归算法设计数据结构递归算法先考虑将物品mn放入背包的情况：knap(m,n)=•若mn=m,则knap(m,n)←true•若mnm,则knap(m,n)←knap(m,n-1)即放弃mn物品，从n-1中选取•否则mnm，则knap(m,n)←knap(m,n-1)＋knap(m-mn,n-1)即如果选中mn，问题转化为knap(m-mn,n-1)是否有解；如果无解，放弃mn物品问题转化为knap(m,n-1)是否有解。3.递归算法设计数据结构递归算法boolknap(m,n){if(n==1){//出口条件if(m[1]==m)returntrue;elsereturnfalse;}if(m[n]==m)returntrue;if(m[n]m)returnknap(m,n-1);if(knap(m-m[n],n-1))returntrue;returnknap(m,n-1);}3.递归算法设计数据结构递归算法棋子移动问题描述：有2n（n3）个棋子排成一行，白子用0代表，黑子用1代表。n=5的状态为：0000011111__(右边至少两个空位)移动规则：(1)每次必须移动相邻的两个棋子，这两个棋子不能互换位置(2)移动的颜色不限，移动的方向不限要求：最后成为__0101010101的状态(中间无空格)。3.递归算法设计数据结构递归算法N=4,(4,5)---(9,10)n=6,(6,7)---(13,14)(8,9)---(4,5)(11,12)---(6,7)(2,3)---(8,9)n=5(7,8)---(2,3)(1,2)---(7,8)N=5,(5,6)---(11,12)(9,10)---(5,6)n=4由数学归纳法可知；递归出口为n=4数据结构递归算法如果2n个棋子的移动用chess(n)则递归关系move（n,n+1)—(2n+1,2n+2)move(2n-1,2n)—(n,n+1)chess(n-1)数据结构递归算法(1)空格在任何地方都是可等价变换的(2)问题规模为n和为n-1有相似的地方吗？000……000111……111__(问题的规模n)000……0011……111__01(问题的规模n-1,?)结论：(1)规模为n的问题可以通过两步的移动变成规模为n-1的问题!(2)初值（递归的结束条件n=?可以解）3.递归算法设计数据结构递归算法1.初值的判断：n=2,0011__→0__101→010__1,无解n=3,无解n=4:(1)00001111__(2)000__11101(3)0001011__1(4)0__1011001(5)010101__01(6)__010101013.递归算法设计数据结构递归算法2.递推关系式:(1)000...000111...111__(n)(2)000...00__11...11101(3)000...001111...1__01(n-1)(4)对n-1个棋子进行递归的移动直到n=4为止3.递归算法设计数据结构递归算法3.算法实现：(对棋子的位置进行编号，从1,2,2n,2n+1,2n+2)voidchess(intn){//n为移动的棋子数，n≥4if(n==4){//递归出口……}elseif(n4){//进入递归move_to(n,n+1,2n+1,2n+2);move_to(2n-1,2n,n,n+1);chess(n-1);}}3.递归算法设计数据结构递归算法4.思考：如果棋子的移动规则改为每次移动相邻的3个(4,5,…)棋子，其他条件不变，则如何解决此问题？(1)递归关系式的推导(2)初值的判断(n=?有解)(3)算法的实现3.递归算法设计数据结构递归算法Hanoi塔问题汉诺塔（TowerofHanoi）游戏据说来源于布拉玛神庙。游戏的装置如图所示（图上以3个金片例），底座上有三根金的针，第一根针上放着从大到小64个金片。游戏的目标是把所有金片从第一根针移到第三根针上，第二根针作为中间过渡。每次只能移动一个金片，并且大的金片不能压在小的金片上面。该游戏的结束就标志着“世界末日”的到来。3.递归算法设计ABC三个金片的Hanoi游戏的装置数据结构递归算法分析：◆游戏中金片移动是一个很繁琐的过程。通过计算，对于64个金片至少需要移动264–1=1.6×1019次。■不妨用A表示被移动金片所在的针（源），C表示目的针，B表示过渡针。对于把n（n1）个金片从第一根针A上移到第三根针C的问题可以分解成如下步骤：（1）将n-1个金片从A经过C移动到B。（2）将第n个金片移动到C。（3）再将n-1个金片从B经过A移动到C。这样就把移动n个金片的问题转化为移动n-1个金片的问题，即移动n个金片的问题可用移动n-1个金片的问题递归描述，以此类推，可转化为移动一个金片的问题。显然，一个金片就可以直接移动。3.递归算法设计ABC三个金片的Hanoi游戏的装置数据结构递归算法voidhanoi(intn,inta,intb,intc){if(n1){hanoi(n-1,a,c,b);move(n,a,b);hanoi(n-1,b,a,c);}elsemove(n,a,b);//结束条件}3.递归算法设计数据结构递归算法n个元素的全排列N=1,输出1N=2,输出1,22,1N=3,输出1,2,31,3,22,1,32,3,13,1,23,2,1解决：(1)递推关系式(2)初始值(递归的出口)(3)算法实现3.递归算法设计数据结构递归算法a[]={1,2.3,4,…,n};//对a[k]–a[n]进行全排列voidRange(a,k,n){if(k==n)Print(a);//输出排列else{for(i=k;in;i++){a[k]↔a[i];//交换值Range(a,k+1,n);//递归排列剩下的元素a[i]↔a[k];//交换值}}}初始调用：Range(a,0,n);3.递归算法设计数据结构递归算法数据结构递归算法3.递归关系式的计算递归算法时间复杂度的分析递归算法时间复杂度的计算4.递归关系式计算数据结构递归算法递归算法时间复杂度分析根据递归算法思想，可以得到递归算法的时间复杂度的递推关系式求解递推关系式即可4.递归关系式计算数据结构递归算法例：一个楼有n个台阶，有一个人上楼有时一次跨一个台阶，有时跨2个台阶。问此人共有几种不同的上楼方法，并分析算法的时间复杂度。解：设H(n)为上楼的方法总数，则：①当n=1,H(1)=1②当n=2,H(2)=2③