算法与数据结构第6章递归

《算法与数据结构第6章递归》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章递归6.1什么是递归6.2递归算法的设计本章小结6.1什么是递归6.1.1递归的定义在定义一个过程或函数时出现调用本过程或本函数的成分,称之为递归。若调用自身,称之为直接递归。若过程或函数p调用过程或函数q,而q又调用p,称之为间接递归。如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。例以下是求n!(n为正整数)的递归函数。intfun(intn){if(n==1)//语句1return1;//语句2else//语句3returnfun(n-1)*n;//语句4}在该函数fun(n)求解过程中,

2、直接调用fun(n-1)(语句4)自身,所以它是一个直接递归函数。又由于递归调用是最后一条语句,所以它又属于尾递归。6.1.2何时使用递归在以下三种情况下,常常要用到递归的方法。1.定义是递归的有许多数学公式、数列等的定义是递归的。例如,求n!和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。思考题：指出正整数的定义。2.数据结构是递归的有些数据结构是递归的。例如,第2章中介绍过的单链表就是一种递归数据结构,其结点类型定义如下：typedefstructLNode{ElemTypedata;struc

3、tLNode*next;}LinkList;该定义中,结构体LNode的定义中用到了它自身,即指针域next是一种指向自身类型的指针,所以它是一种递归数据结构。对于递归数据结构,采用递归的方法编写算法既方便又有效。例如,求一个不带头结点的单链表head的所有data域(假设为int型)之和的递归算法如下：intSum(LinkList*head){if(head==NULL)return0;elsereturn(head->data+Sum(head->next));}3.问题的求解方法是递归的有些问题的解法是递归的,典型的有Hanoi问

4、题求解,该问题描述是：设有3个分别命名为X,Y和Z的塔座,在塔座X上有n个直径各不相同,从小到大依次编号为1,2,…,n的盘片,现要求将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个圆盘从

5、x移到z；Hanoi(n-1,y,x,z)6.1.3递归模型递归模型是递归算法的抽象,它反映一个递归问题的递归结构,例如,前面的递归算法对应的递归模型如下：fun(1)=1(1)fun(n)=n*fun(n-1)n>1(2)其中,第一个式子给出了递归的终止条件,第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系,我们把第一个式子称为递归出口,把第二个式子称为递归体。一般地,一个递归模型是由递归出口和递归体两部分组成,前者确定递归到何时结束,后者确定递归求解时的递推关系。递归出口的一般格式如下：f(s1)=m1(6.1)这里的

6、s1与m1均为常量,有些递归问题可能有几个递归出口。递归体的一般格式如下：f(sn+1)=g(f(si),f(si+1),…,f(sn),cj,cj+1,…,cm)(6.2)其中,n,i,j,m均为正整数。这里的sn+1是一个递归“大问题”,si,si+1,…,sn为递归“小问题”,cj,cj+1,…,cm是若干个可以直接(用非递归方法)解决的问题,g是一个非递归函数,可以直接求值。实际上,递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决,再把这些“小问题”进一步分解成更小的“小问题”来解决,如此分解,直至每

7、个“小问题”都可以直接解决(此时分解到递归出口)。但递归分解不是随意的分解,递归分解要保证“大问题”与“小问题”相似,即求解过程与环境都相似。为了讨论方便,简化上述递归模型为：f(s1)=m1(6.3)f(sn)=g(f(sn-1),c)(6.4)求f(sn)的分解过程如下：f(sn)↓f(sn-1)↓…↓f(s2)↓f(s1)一旦遇到递归出口,分解过程结束,开始求值过程,所以分解过程是“量变”过程,即原来的“大问题”在慢慢变小,但尚未解决,遇到递归出口后,便发生了“质变”,即原递归问题便转化成直接问题。上面的求值过程如下：f(s1)=m

8、1↓f(s2)=g(f(s1),c1)↓f(s3)=g(f(s2),c2)↓…↓f(sn)=g(f(sn-1),cn-1)这样f(sn)便计算出来了,因此,递归的执行过程由分解和求值两部分构成