《【考研计算机专业课】武汉大学数据结构PPT课件第6章递归》由会员分享，可在线阅读，更多相关《【考研计算机专业课】武汉大学数据结构PPT课件第6章递归（56页珍藏版）》请在金锄头文库上搜索。
1、第6章 递归,6.1 什么是递归,6.2 递归算法的设计,6.1 什么是递归 6.1.1 递归的定义在定义一个过程或函数时出现调用本过程或本函数的成分,称之为递归。若调用自身,称之为直接递归。若过程或函数p调用过程或函数q,而q又调用p,称之为间接递归。 如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。,例如，以下是求n!(n为正整数)的递归函数。int fun(int n) if (n=1) /语句1return 1; /语句2else /语句3return fun(n-1)*n; /语句4在该函数fun(n)求解过程中,直接调用fun(n-1)(语句4
2、)自身,所以它是一个直接递归函数。又由于递归调用是最后一条语句,所以它又属于尾递归。,6.1.2 何时使用递归在以下三种情况下,常常要用到递归的方法。1. 定义是递归的有许多数学公式、数列等的定义是递归的。例如,求n!和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。,思考题：指出正整数的定义。,2. 数据结构是递归的有些数据结构是递归的。例如,第2章中介绍过的单链表就是一种递归数据结构,其结点类型定义如下：typedef struct LNode ElemType data;struct LNode *next; LinkList;该定义中,结构体LNo
3、de的定义中用到了它自身,即指针域next是一种指向自身类型的指针,所以它是一种递归数据结构。,为什么可以这样递归定义类型,对于递归数据结构,采用递归的方法编写算法既方便又有效。例如,求一个不带头结点的单链表L的所有data域(假设为int型)之和的递归算法如下：int Sum(LinkList *L) if (L=NULL)return 0;else return(L-data+Sum(L-next);,3. 问题的求解方法是递归的有些问题的解法是递归的,典型的有Hanoi问题求解,该问题描述是：设有3个分别命名为X,Y和Z的塔座,在塔座X上有n个直径各不相同,从小到大依次编号为1,2,n的
4、盘片,现要求将X塔座上的n个盘片移到塔座Z上并仍按同样顺序叠放,盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在X,Y和Z中任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。设计递归求解算法,并将其转换为非递归算法。设Hanoi(n,x,y,z)表示将n个盘片从x通过y移动到z上,递归分解的过程是：,Hanoi(n,x,y,z),Hanoi(n-1,x,z,y)； move(n,x,z):将第n个圆盘从x移到z； Hanoi(n-1,y,x,z),6.1.3 递归模型递归模型是递归算法的抽象,它反映一个递归问题的递归结构,例如,前面的递归算法对应的递归模型如下：fun(1
5、)=1 (1) fun(n)=n*fun(n-1) n1 (2)其中,第一个式子给出了递归的终止条件,第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系,我们把第一个式子称为递归出口,把第二个式子称为递归体。,一般地,一个递归模型是由递归出口和递归体两部分组成,前者确定递归到何时结束,后者确定递归求解时的递推关系。递归出口的一般格式如下：f(s1)=m1 (6.1)这里的s1与m1均为常量,有些递归问题可能有几个递归出口。递归体的一般格式如下：f(sn+1)=g(f(si),f(si+1),f(sn),cj,cj+1,cm) (6.2)其中,n,i,j,m均为正整数。这里的sn+
6、1是一个递归“大问题”,si,si+1,sn为递归“小问题”,cj,cj+1,cm是若干个可以直接(用非递归方法)解决的问题,g是一个非递归函数,可以直接求值。,递归思路是：把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决；再把这些“小问题”进一步分解成更小的“小问题”来解决；如此分解,直至每个“小问题”都可以直接解决(此时分解到递归出口)。但递归分解不是随意的分解,递归分解要保证“大问题”与“小问题”相似,即求解过程与环境都相似。,为了讨论方便,简化上述递归模型为：f(s1)=m1 (6.3)f(sn)=g(f(sn-1),cn-1) (6.4) 求f(sn)的分解过程如
7、下：f(sn)f(sn-1)f(s2)f(s1),一旦遇到递归出口,分解过程结束,开始求值过程,所以分解过程是“量变”过程,即原来的“大问题”在慢慢变小,但尚未解决,遇到递归出口后,便发生了“质变”,即原递归问题便转化成直接问题。上面的求值过程如下：f(s1)=m1f(s2)=g(f(s1),c1)f(s3)=g(f(s2),c2)f(sn)=g(f(sn-1),cn-1),这样f(sn)便计算出来了,因此,递归的执行过程由分解和求值两部分构成。,求解fun(5)的过程如下：,F(1)=0 F(2)=1 F(n)=F(n-1)+F(n-2) n=2,F(5),F(4),F(3),F(2),F(
8、1),F(1),F(0),F(2),F(1),F(0),F(3),F(2),F(1),F(1),F(0),递归树,思考题：递归的本质是什么？,6.2 递归算法的设计递归的求解的过程均有这样的特征：先将整个问题划分为若干个子问题,通过分别求解子问题,最后获得整个问题的解。而这些子问题具有与原问题相同的求解方法,于是可以再将它们划分成若干个子问题,分别求解,如此反复进行,直到不能再划分成子问题,或已经可以求解为止。这种自上而下将问题分解、求解,再自上而下引用、合并,求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。递归算法设计先要给出递归模型,再转换成对应的C/C+语言函数。,求
9、递归模型的步骤如下：（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时等式成立相似)。,例如,采用递归算法求实数数组A0n-1中的最小值。假设f(A,i)函数求数组元素A0Ai中的最小值。当i=0时,有f(A,i)=A0；假设f(A,i-1)已求出,则f(A,i)=MIN(f(A,i-1),Ai),其中
10、MIN()为求两个值较小值函数。因此得到如下递归模型：,f(A,i)=A0 当i=0时 f(A,i)= MIN(f(A,i-1),Ai) 其他情况,由此得到如下递归求解算法：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;,例如，设计不带头结点的单链表的相关递归算法,a1,a2,an,.,L,f(L)：大问题,f(L-next)：小问题,为什么在设计单链表的递归算法时不带头结点？,（1）求单链表中数据结点个数,递归模型如下：,f(L)=0 当L=
11、NULL f(L)=f(L-next)+1 其他情况,int count(Node *L) if (L=NULL)return 0;elsereturn count(L-next)+1; ,递归算法如下：,（2）正向显示以L为首节点指针的单链表的所有节点值,递归模型如下：,f(L)不做任何事件 当L=NULL f(L)输出L-data;f(L-next) 其他情况,void traverse(Node *L) if (L=NULL) return;printf(“%d “,L-data);traverse(L-next); ,递归算法如下：,（3）反向显示以L为首节点指针的单链表的所有节点值,
12、递归模型如下：,f(L)不做任何事件 当L=NULL f(L)f(L-next);输出L-data; 其他情况,void traverseR(Node *L) if (L=NULL) return;traverseR(L-next);printf(“%d “,L-data); ,递归算法如下：,（4）删除以L为首节点指针的单链表中值为x的第一个节点,递归模型如下：,f(L,x)不做任何事件 当L=NULL f(L,x) 删除L所指结点 当L-data=x f(L,x)f(L-next,x) 其他情况,void del(Node * ,递归算法如下：,（5）删除以L为首节点指针的单链表中值为x的
13、所有节点,递归模型如下：,f(L,x)不做任何事件 当L=NULL f(L,x) 删除L所指结点;f(L-next,x) 当L-data=x f(L,x) f(L-next,x) 其他情况,void delall(Node * ,递归算法如下：,（6）输出以L为首节点指针的单链表中最大节点值,递归模型如下：,f(L)=L-data 当L中只有一个结点 f(L)=MAX(f(L-next),L-data) 其他情况,ElemType maxv(Node *L) ElemType m;if (L-next=NULL)return L-data;m=maxv(L-next);if (mL-data)
14、 return m;else return L-data; ,递归算法如下：,（7）输出以L为首节点指针的单链表中最小节点值。,递归模型如下：,f(L)=L-data 当L中只有一个结点 f(L)=MIN(f(L-next),L-data) 其他情况,ElemType minv(Node *L) ElemType m;if (L-next=NULL)return L-data;m=minv(L-next);if (mL-data) return L-data;else return m; ,递归算法如下：,（8）释放L为首节点指针的单链表的所有节点,递归模型如下：,f(L)不做任何事件 当L=
15、NULL f(L)f(L-next);释放L所指结点; 其他情况,void Destroy(Node *L) if (L=NULL) return;Destroy(L-next);free(L); ,递归算法如下：,例如，求1，2，n的全排列。设a是含n个不同字符的字符串，f(a,k-1,n)为a0k-1的所有字符的全排序，f(a,k,n)为a0k的所有字符的全排序。假设f(a,k-1,n)可求，对于ak位置，可以取a0k任何之值，再组合f(a,k-1,n)，则得到f(a,k,n)递归模型为：,f(a,k,n)：输出a 当k=0时 f(a,k,n)：ak位置取a0k任何之值, 其他情况并组合f(a,k-1,n)的结果;,此位置可以取a0ak中任何值，但不重复！,例如，求a=“123”的全排列（下标为02），f(a,2,3) ：,位置2：此处放1（即1和3交换），32的全排列有23、32，输出231、321此处放2（即2和3交换），13的全排列有13、31，输出312、132此处放3（即3和3交换），12的全排列有21、12，输出213、123,
