资源描述：
《递归算法到非递归算法的转换课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第6章递归6.3递归算法到非递归算法的转换6.1什么是递归6.2递归算法的设计本章小结6.1什么是递归6.1.1递归的定义在定义一个过程或函数时出现调用本过程或本函数的成分,称之为递归。若调用自身,称之为直接递归。若过程或函数p调用过程或函数q,而q又调用p,称之为间接递归。例求n!(n为正整数)。一般的方法：n!=1*2*…*(n-1)*n递归的方法：intfactorial(intn){intx;if(n==0)x=1;elsex=factorial(n-1)*n;return(x);}在该函数facto
2、rial(n)求解过程中,直接调用factorial(n-1)自身,所以它是一个直接递归函数。intfactorial(intn){intx;if(n==0)x=1;elsex=factorial(n-1)*n;return(x);}n=4n=3n=2n=1n=06.1.2何时使用递归在以下三种情况下,常常要用到递归的方法。1.定义是递归的2.数据结构是递归的3.问题的求解方法是递归的1.定义是递归的有许多数学公式、数列等的定义是递归的。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。例如,求Fi
3、bonacci数列:2.数据结构是递归的有些数据结构是递归的。例如,第2章中介绍过的单链表就是一种递归数据结构,其结点类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LinkList;对于递归数据结构,采用递归的方法编写算法既方便又有效。例如,求一个不带头结点的单链表head的所有data域(假设为int型)之和的递归算法：intSum(LinkList*head){if(head==NULL)return0;elsereturn(head->
4、data+Sum(head->next));}3.问题的求解方法是递归的有些问题的解法是递归的,典型的有汉诺塔(TowerofHanoi)问题求解：盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在A,B和C中任一塔座；不能将一个较大的盘片放在较小的盘片上。Hanoi(n,a,b,c)Hanoi(n-1,a,c,b)；move(n,a,c)；Hanoi(n-1,b,a,c)6.1.3递归模型递归模型是递归算法的抽象,它反映递归问题的递归结构,例如,前面的递归算法对应的递归模型如下：fun(0)=1
5、n=0(1)fun(n)=n*fun(n-1)n>0(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
6、,…,cm)(6.2)其中,n,i,j,m均为正整数。sn+1是一个递归“大问题”,si,si+1,…,sn为递归“小问题”,cj,cj+1,…,cm是可以用非递归方法直接解决的问题g是一个非递归函数,可以直接求值。递归思路实际上,递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决,再把这些“小问题”进一步分解成更小的“小问题”来解决,如此分解,直至每个“小问题”都可以直接解决(此时分解到递归出口)。但递归分解不是随意的分解,递归分解要保证“大问题”与“小问题”相似,即求解过程与环
7、境都相似。并且有一个分解的终点。从而使问题可解。求解5!的过程如下：斐波那契数列的递归调用树递归的执行过程由分解过程和求值过程两部分构成。分解过程是“量变”过程,即原来的“大问题”在慢慢变小,但尚未解决；遇到递归出口后,便发生了“质变”,即原递归问题便转化成直接问题。6.2递归算法的设计递归的求解的过程均有这样的特征：先将整个问题划分为若干个子问题,通过分别求解子问题,最后获得整个问题的解。而这些子问题具有与原问题相同的求解方法,于是可以再将它们划分成若干个子问题,分别求解,如此反复进行,直到不能再划分成子问
8、题,或已经可以求解为止。这种自上而下将问题分解、求解,再自上而下引用、合并,求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。递归算法设计先要给出递归模型,再转换成对应的C/C++语言函数。递归设计的步骤如下：(1)对原问题f(s)进行分析,假设出合理的“较小问题”f(s')(与数学归纳法中假设n=k-1时等式成立相似)；(2)假设f(s')是可解的,在此基础上确定f(s)的解,即
