资源描述：
《专题讲座--非递归化(zsl)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、主要内容什么时候使用递归递归分类递归模型递归算法的执行过程递归算法的效率分析递归算法的非递归化处理一、什么时候使用递归？1.问题的定义是递归的有许多数学公式、数列等的定义是递归的。例如,求n!和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。例如：阶乘函数的定义1当n=0时n！=n*(n-1)*…*1当n>0时1当n=0时n！=n*(n-1)！当n>0时这时候递归的定义可以用如下的函数表示：1当n=0时f(n)=n*f(n-1)当n>0时也就是说，函数f(n)的定义用到了自己本身f(n－1)第一种递归阶乘的另外一种定义方法有些数据结构是递归
2、的。例如,单链表就是一种递归数据结构,其结点类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LinkList;该定义中,结构体LNode的定义中用到了它自身,即指针域next是一种指向自身类型的指针,所以它是一种递归数据结构。2.数据结构是递归的第二种递归对于递归数据结构,采用递归的方法编写算法既方便又有效。例如,求一个不带头结点的单链表head的所有data域(假设为int型)之和的递归算法如下：intSum(LinkList*head){if(head==NULL)return0;elsereturn(hea
3、d->data+Sum(head->next));}一个典型的例子是在有序数组中查找一个数据元素是否存在的折半查找算法有序数组元素为1；3；4;5;17;18;31;33;寻找值为17的数据3.问题的求解方法是递归的第三种递归典型的三种情况使用递归：问题的定义是递归的数据结构是递归的问题求解的过程是递归的直接递归：函数直接调用本身。A(){……CALLA()......}间接递归：一函数在调用其他函数时，又产生了对自身的调用。A()B(){……{……CALLB（）CALLA（）……}……}二、递归分类递归模型是递归算法的抽象,它反映一个递归问题的递归结构,例如,前面的递归算法对
4、应的递归模型如下：fun(1)=1(1)fun(n)=n*fun(n-1)n>1(2)其中,第一个式子给出了递归的终止条件,第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系,第一个式子称为递归出口,第二个式子称为递归体。三、递归模型一般地,一个递归模型是由递归出口和递归体两部分组成,前者确定递归到何时结束,后者确定递归求解时的递推关系。实际上递归的思路是把一个不能或者不好直接求解的“大问题”转化为一个或者几个“小问题”来解决；再把“小问题”进一步分解为更小的“小问题”来解决；如此分解，直到“小问题”可以直接求解。递归模型的分解过程不是随意分解，分解问题规模要保证
5、“大问题”和“小问题”的相似性，即求解过程和环境要具备相似性；一旦遇到递归出口，分解过程结束，开始求值，分解是量变的过程，大问题慢慢变小，但是尚未解决，遇到递归出口之后，发生了质变，即递归问题转化为直接问题。因此，递归算法的执行总是分为分解和求值两个部分。递归出口的一般格式如下f(s1)=m1递归体的一般格式f(sn)=g(f(sn-1),c)递归的分解过程递归求值的过程递归的求解的过程均有这样的特征：先将整个问题划分为若干个子问题,通过分别求解子问题,最后获得整个问题的解。而这些子问题具有与原问题相同的求解方法,于是可以再将它们划分成若干个子问题,分别求解,如此反复进行,直到
6、不能再划分成子问题,或已经可以求解为止。这种自上而下将问题分解、求解,再自上而下引用、合并,求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。四、递归算法执行过程以阶乘的递归计算为例longFact(intn){longf;if(n<0)printf("n<0,inputerror");elseif(n==0
7、
8、n==1)f=1;elsef=Fact(n-1)*n;return(f);}执行过程分析递归算法执行过程总结递归算法的执行过程是不断地自调用，直到到达递归出口才结束自调用过程；到达递归出口后，递归算法开始按最后调用的过程最先返回的次序返回；返回到最外层
9、的调用语句时递归算法执行过程结束。五、递归算法的效率分析斐波那契数列Fib(n)的递归定义是：求第n项斐波那契数列的递归函数如下：longFib(intn){if(n==0
10、
11、n==1)returnn;//递归出口elsereturnFib(n-1)+Fib(n-2);//递归调用}斐波那契数列计算的调用过程用归纳法可以证明求Fib(n)的递归调用次数等于2n-1；计算斐波那契数列的递归函数Fib(n)的时间复杂度为O(2n)。计算斐波那契数列Fib(n)问题，我们也可根据公式写出循环方式求
