数据结构递归.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,递归,3 递归算法到非递归算法的转换,1 什么是递归,2 递归算法的设计,1,.,1,什么是递归,1.1 递归的定义,在定义一个过程或函数时出现调用本过程或本函数的成分,称之为,递归,。若调用自身,称之为直接递归。若过程或函数p调用过程或函数q,而q又调用p,称之为,间接递归,。,如果一个,递归过程,或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为,尾递归,。,2,.,例1 以下是求n!(n为正整数)的递归函数。,int fun(int n),int x;,if(n=1)/*语句1*/,x=1;/*语句2*/,else/*语句3*/,x=fun(n-1)*n;/*语句4*/,return(x);/*语句5*/,在该函数fun(n)求解过程中,直接调用fun(n-1)(语句4)自身,所以它是一个直接递归函数。又由于递归调用是最后一条语句,所以它又属于尾递归。,3,.,1.2 何时使用递归,在以下三种情况下,常常要用到递归的方法。,1.定义是递归的,有许多数学公式、数列等的定义是递归的。例如,求n!和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。,4,.,2.,数据结构是递归的,有些数据结构是递归的。例如,第2章中介绍过的单链表就是一种递归数据结构,其结点类型定义如下：,typedef struct LNode,ElemType data;,struct LNode*next;,LinkList;,该定义中,结构体LNode的定义中用到了它自身,即指针域next是一种指向自身类型的指针,所以它是一种递归数据结构。,5,.,对于递归数据结构,采用递归的方法编写算法既方便又有效。例如,求一个不带头结点的单链表head的所有data域(假设为int型)之和的递归算法如下：,int Sum(LinkList*head),if(head=NULL),return 0;,else,return(head-data+Sum(head-next);,6,.,3.,问题的求解方法是递归的,有些问题的解法是递归的,典型的有Hanoi问题求解,该问题描述是：,设有3个分别命名为X,Y和Z的塔座,在塔座X上有n个直径各不相同,从小到大依次编号为1,2,n的盘片,现要求将X塔座上的n个盘片移到塔座Z上并仍按同样顺序叠放,盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在X,Y和Z中任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。,设计递归求解算法,并将其转换为非递归算法。,设Hanoi(n,x,y,z)表示将n个盘片从x通过y移动到z上,递归分解的过程是：,7,.,Hanoi(n,x,y,z),Hanoi(n-1,x,z,y)；,move(n,x,z):将第n个圆盘从x移到z；,Hanoi(n-1,y,x,z),8,.,1.3 递归模型,递归模型是递归算法的抽象,它反映一个递归问题的递归结构,例如,前面的递归算法对应的递归模型如下：,fun(1)=1 (1),fun(n)=n*fun(n-1)n1 (2),其中,第一个式子给出了递归的终止条件,第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系,我们把第一个式子称为,递归出口,把第二个式子称为,递归体,。,9,.,一般地,一个递归模型是由,递归出口和递归体,两部分组成,前者确定递归到何时结束,后者确定递归求解时的递推关系。递归出口的一般格式如下：,f(s,1,)=m,1,(3.1),这里的s,1,与m,1,均为常量,有些递归问题可能有几个递归出口,。递归体的一般格式如下：,f(s,n+1,)=g(f(s,i,),f(s,i+1,),f(s,n,),c,j,c,j+1,c,m,)(3.2),其中,n,i,j,m均为正整数。这里的s,n+1,是一个递归“大问题”,s,i,s,i+1,s,n,为递归“小问题”,c,j,c,j+1,c,m,是若干个可以直接(用非递归方法)解决的问题,g是一个非递归函数,可以直接求值。,10,.,实际上,递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决,再把这些“小问题”进一步分解成更小的“小问题”来解决,如此分解,直至每个“小问题”都可以直接解决(此时分解到递归出口)。但递归分解不是随意的分解,递归分解要保证“大问题”与“小问题”相似,即求解过程与环境都相似。,11,.,为了讨论方便,简化上述递归模型为：,f(s,1,)=m,1,(3),f(s,n,)=g(f(s,n-1,),c)(4),求f(s,n,)的分解过程如下：,f(s,n,),f(s,n-1,),f(s,2,),f(s,1,),12,.,一旦遇到递归出口,分解过程结束,开始求值过程,所以分解过程是“量变”过程,即原来的“大问题”在慢慢变小,但尚未解决,遇到递归出口后,便发生了“质变”,即原递归问题便转化成直接问题。上面的求值过程如下：,f(s,1,)=m,1,f(s,2,)=g(f(s,1,),c,1,),f(s,3,)=g(f(s,2,),c,2,),f(s,n,)=g(f(s,n-1,),c,n-1,),13,.,这样f(s,n,)便计算出来了,因此,递归的执行过程由,分解和求值,两部分构成。,14,.,求解fun(5)的过程如下：,15,.,2 递归算法的设计,递归的求解的过程均有这样的特征：,先将整个问题划分为若干个子问题,通过分别求解子问题,最后获得整个问题的解,。而这些子问题具有与原问题相同的求解方法,于是可以再将它们划分成若干个子问题,分别求解,如此反复进行,直到不能再划分成子问题,或已经可以求解为止。这种自上而下将问题分解、求解,再自上而下引用、合并,求出最后解答的过程称为递归求解过程。这是一种,分而治之,的算法设计方法。,递归算法设计先要给出递归模型,再转换成对应的C/C+语言函数。,16,.,递归设计的步骤如下：,(1)对原问题f(s)进行分析,假设出合理的“较小问题”f(s)(与数学归纳法中假设n=k-1时等式成立相似)；,(2)假设f(s)是可解的,在此基础上确定f(s)的解,即给出f(s)与f(s)之间的关系(与数学归纳法中求证n=k时等式成立的过程相似)；,(3)确定一个特定情况(如f(1)或f(0)的解,由此作为递归出口(与数学归纳法中求证n=1时等式成立相似)。,17,.,例如,采用递归算法求实数数组A0.n-1中的最小值。,假设f(A,i)函数求数组元素A0Ai中的最小值。,当i=0时,有f(A,i)=A0；,假设f(A,i-1)已求出,则f(A,i)=MIN(f(A,i-1),Ai),其中MIN()为求两个值较小值函数。因此得到如下递归模型：,A0 当i=0时,f(A,i)=,MIN(f(A,i-1),Ai)其他情况,18,.,由此得到如下递归求解算法：,float f(float A,int i),float m;,if(i=0),return A0;,else,m=f(A,i-1);,if(mAi),return Ai;,else,return m;,19,.,3 递归算法到非递归算法的转换,递归算法有两个基本特性：,一是递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题方法,对求解某些复杂问题,递归算法分析问题的方法是十分有效的；,二是递归算法的时间效率通常比较差,。,因此,对求解某些问题时,我们希望用递归算法分析问题,用非递归算法具体求解问题。这就需要把递归算法转换为非递归算法。,20,.,把递归算法转化为非递归算法有如下三种基本方法：,(1)对于尾递归和单向递归的算法,可用循环结构的算法替代。,(2)自己用栈模拟系统的运行时栈,通过分析只保存必须保存的信息,从而用非递归算法替代递归算法。,(3)利用栈保存参数,由于栈的后进先出特性吻合递归算法的执行过程,因而可以用非递归算法替代递归算法。,本节讨论第(1)种和第(2)种情况的递归算法转化为非递归算法的问题,前者是一种是直接转化法,不需要使用栈,后者是间接转化法,需要使用栈。第(3)种情况也需要使用栈,但因具体情况而异,例如树的遍历算法。,21,.,3.1 尾递归和单向递归的消除,采用循环结构消除尾递归和单向递归。求解Fibonacci数列的算法如下：,int Fib(int n),int i,f1,f2,f3;,if(n=1|n=2)return(n);,f1=1;f2=2;,for(i=3;i-1)/*栈不空时循环*/,if(Sttop.tag=1)/*未计算出栈顶元素的vf值*/,if(Sttop.vn=1)/*(1)式*/,Sttop.vf=1;,Sttop.tag=0;,else/*(2)式*/,top+;,Sttop.vn=Sttop-1.vn-1;Sttop.tag=1;,27,.,else if(Sttop.tag=0)/*已计算出vf值*/,Sttop-1.vf=Sttop-1.vn*Sttop.vf;/*(2)式*/,Sttop-1.tag=0;,top-;,if(top=0&Sttop.tag=0),/*栈中只有一个已求出vf的元素时退出循环*/,break;,return(Sttop.vf);,28,.,小结,基本学习要点如下：,(1)理解递归的定义和递归模型。,(2)重点掌握递归的执行过程。,(3)掌握递归设计的一般方法。,(4)掌握消除递归的基本方法。,(5)灵活运用递归算法解决一些较复杂应用问题。,29,.,