数据结构-递归算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构 递归算法,递归算法(Recursion),本章内容,递归算法定义,递归算法举例,递归算法复杂性的计算,递归算法,递归(Recursion)定义,直接或间接地调用自身的算法称为,递归算法,直接或间接调用自身的函数称为,递归函数,尾递归,是指递归调用的语句在递归函数的最后一句,递归算法的特点：,用于解决一类,递归定义,的问题,算法易于实现，简单明了,递归算法,递归算法：,1 (n=0,1),n!=,n(n-1)！(n1),函数的递归调用,1.定义：,在调用一个函数的过程中直接或间接地调用该函数本身。,直接调用,int f(x),int x;,int y,z;,.,z=f(x);,return(2*z);,f 函数,调用 f函数,int f1(x),int x;,int y,z;,.,z=f2(y);,return(2*z);,int f2(t),int t;,int a,c;,.,c=f1(a);,return(3+c);,间接调用,特点,是无终止的递归调用，因此，,应该给定一个限制递归次数的条件。,f 1函数,调用 f2函数,f 2函数,调用 f1函数,float fac(int n),float f;,if(n0)printf(“n1),算法 求斐波那契数,procedure F(n),/返回第n个斐波那契数/,integer n,if n,1 then return(1),else return(F(n-1)+F(n-2),endif,end F,算法效率：对F(n-1)、F(n-2)存在大量的重复计算，可以改进算法：保存中间结果,例1.4 欧几里得算法,已知两个非负整数a和b，且a,b0，求这两个数的最大公因数。,辗转相除法,：若b=0，则a和b的最大公因数等于a；若b0，则a和b的最大公因数等于b和用b除a的余数的最大公因数。,算法1.8 求最大公因数,procedure GCD(a,b)/约定ab/,if b=0 then return(a),else return(GCD(b,a mod b),endif,end GCD,例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;,例1.5 递归在,非数值算法,设计中的应用,已知元素x，判断x是否在A（1：n）中。,算法 在A（1：n）中检索x,procedure SEARCH(i),/如果在A（1：n）/中有一元素A（k）=x，则将其第一次出现的下标k返回，否则返回0/,global n,x,A(1:n),case,:in:return(0),:A(i)=x;return(i),:else:return(SEARCH(i+1),endcase,end SEARCH,子程序的调用形式,递归算法的实现机制,主程序,Call A,1:,子程序A,一次调用,主程序,Call A,1:,Call A,2:,子程序A,多次调用,1,STACK,1/,2,STACK,主程序,Call A,1:,子程序A,Call B,2:,子程序B,嵌套调用,子程序A,主程序,Call B,1:,子程序B,Call A,2:,平行调用,递归算法的实现机制,1,2,STACK,1,2,STACK,2.递归算法设计,定义递归（数学公式，数列等的定义。）,数据结构递归（单链表，树，二叉树）,可用递归解决的问题P（hanoi问题）,问题P具有大规模,不同规模的问题P，具有相同性质；并且大规模的问题由小规模的问题构成,小规模的问题是可解的,关键：,找到递归的,递推关系,找到,结束递归,的条件,3.递归算法设计,递归求解的伪代码,procedure P(参数表),begin,if 满足递归出口,then 简单操作,else,begin 简单操作;CALL,P,;简单操作;end;,end,endp,3.递归算法设计,简单的0/1背包问题,设一个背包容纳的物品最大质量为m,现有n件物品，质量为m1,m2,mn,均为正整数。要求从中挑选若干件，使背包质量之和正好为m.,（在此问题中，第i件物品要么取，要么不取，不能取一部分，故问题可能有解，可能无解）,设用,knap(m,n),来表示此问题。有解为true,否则为false,3.递归算法设计,先考虑将物品m,n,放入背包的情况：,knap(m,n)=,若,m,n,=m,则,knap(m,n,)true,若,m,n,m,则,knap(m,n,),knap(m,n-1),即放弃,mn,物品，从,n-1,中选取,否则,m,n,m)return knap(m,n-1);,if(knap(m-mn,n-1)return true;,return knap(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),空格在任何地方都是可等价变换的,问题规模为,n,和为,n-1,有相似的地方吗？,000000111111_ _ (,问题的规模,n),0000011111_ _01(,问题的规模,n-1,?),结论：,(1),规模为,n,的问题可以通过两步的移动,变成,规模为,n-1,的问题,!,(2),初值（递归的结束条件,n=?,可以解）,3.递归算法设计,1.初值的判断：,n=2,0011_ _ 0_ _ 101 010_ _ 1,无解,n=3,无解,n=4:,0 0 0,0 1,1 1 1 _ _,0 0 0 _ _ 1,1 1,0 1,0 0 0,1 0,1 1 _ _ 1,0 _ _ 1 0 1 1,0 0,1,0,1 0,1 0 1 _ _ 0 1,_ _ 0 1 0 1 0 1,0 1,3.递归算法设计,2.递推关系式:,0 0 0.0 0 0 1 1 1.1 1 1 _ _ (n),0 0 0.0 0 _ _ 1 1.1 1 1,0 1,0 0 0.0 0,1 1,1 1.1 _ _ 0 1 (n-1),对,n-1,个棋子进行,递归的移动,直到,n=4,为止,3.递归算法设计,3.算法实现：,(对棋子的位置进行编号，从1,2,2n,2n+1,2n+2),void,chess,(int n),/n为移动的棋子数，n4,if(n=4)/递归出口,else if(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,),棋子，其他条件不变，则如何解决此问题？,递归关系式的推导,初值的判断,(n=?,有解,),算法的实现,3.递归算法设计,Hanoi塔问题,汉诺塔（Tower of Hanoi）游戏据说来源于布拉玛神庙。游戏的装置如图所示（图上以3个金片例），底座上有三根金的针，第一根针上放着从大到小64个金片。游戏的目标是把所有金片从第一根针移到第三根针上，第二根针作为中间过渡。每次只能移动一个金片，并且大的金片不能压在小的金片上面。该游戏的结束就标志着“世界末日”的到来。,3.递归算法设计,A,B,C,三个金片的Hanoi游戏的装置,分析：,游戏中金片移动是一个很繁琐的过程。通过计算，对于64个金片至少需要移动 2,64,1=1.610,19,次。,不妨用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.递归算法设计,A,B,C,三个金片的Hanoi游戏的装置,void,hanoi,(int n,int a,int b,int c),if,(n 1),hanoi,(n-1,a,c,b);,move,(n,a,b);,hanoi,(n-1,b,a,c);,else move(n,a,b);/,结束条件,3.递归算法设计,n个元素的全排列,N=1,输出 1,N=2,输出 1,2,2,1,N=3,输出,1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1,解决：,递推关系式,初始值,(,递归的出口,),算法实现,3.递归算法设计,a =1,2.3,4,n;,/对ak an 进行全排列,void,Range,(a,k,n),if(k=n)Print(a);/输出排列,else,for(i=k;i2,时,H(n,)=H(n-1)+H(n-2),下面分析时间复杂度：设为,T(n,),C,n2时,T(n)=,4.递归关系式计算,T(n)2T(n-1)2,2,T(n-2)2,n-1,T(1),=O(2,n,),4.递归关系式计算,时间复杂度的计算-迭代法,0,n=1,2T(n/2)+cn,n1,T(n)=,T(n)=2T(n/2)+cn=2(2T(n/4)+c*n/2)+cn,=2,2,T(n/4)+cn+cn,=2,3,T(n/2,3,)+cn+cn+cn,=,=2,k,T(n/2,k,)+cn+cn+cn,=2k*0+kcn,=cnlog,2,n=,O(nlogn),K个,设 n/2,k,=1,则 k=log,2,n,4.递归关系式计算,求O(T(n)=?,recursion tree（递推树、迭代树）,4.递归关系式计算,汉诺塔（Tower of Hanoi）问题：,假设move所需的时间为1，则其时间复杂度：,1,n=1,2T(n-1)+1,n1,T(n)=,T(n)=2T(n-1)+1=2 2T(n-2)+1+1,=2,2,T(n-2)+2+1=2,3,T(n-3)+2,2,+2+1,=,=2,n-1,T(1)+2,n-2,+2,3,+2,2,+2+1,=2,n-1,+2,n-2,+2,3,+2,2,+2+1,=2,n,-1,若有64个圆盘，则需要移动,2,64,-1=1.610,19,次,4.递归关系式计算,1,n=1,2T(n-1)+n,n1,T(n)=,T(n)=2T(n-1)+n=2 2T(n-2)+n-1+n,=2,2,T(n-2)+2(n-1)+n=2,3,T(n-3)+2,2,(n-2)+2(n-1)+n,=,=2,n-1,T(1)+2,n-2,*2+2,3,(n-3)+2,2,(n-2)+2(n-1)+n,=2,n-1,+2,n-2,*2+2,3,(n-3)+2,2,(n-2)+2(n-1)+n,求O(T(n)=?,4.递归关系式计算,T(n)=2,n-1,+2,n-2,+2,3,+2,2,+2+2,0,+,2,n-2,+2,3,+2,2,+2+2,0,+,+,2,2,+2+2,0,+,2+2,0,+,2,0,=(2,n,-1)+(2,n-1,-1)+(2,2,-1)+(2