专题讲座--非递归化(zsl)

主要内容什么时候使用递归递归分类递归模型递归算法的执行过程递归算法的效率分析递归算法的非递归化处理一、什么时候使用递归？1.问题的定义是递归的有许多数学公式、数列等的定义是递归的。例如,求n!和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。例如：阶乘函数的定义1当n=0时n！=n*(n-1)*…*1当n0时1当n=0时n！=n*(n-1)！当n0时这时候递归的定义可以用如下的函数表示：1当n=0时f(n)=n*f(n-1)当n0时也就是说，函数f(n)的定义用到了自己本身f(n－1)第一种递归阶乘的另外一种定义方法有些数据结构是递归的。例如,单链表就是一种递归数据结构,其结点类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LinkList;该定义中,结构体LNode的定义中用到了它自身,即指针域next是一种指向自身类型的指针,所以它是一种递归数据结构。2.数据结构是递归的第二种递归对于递归数据结构,采用递归的方法编写算法既方便又有效。例如,求一个不带头结点的单链表head的所有data域(假设为int型)之和的递归算法如下：intSum(LinkList*head){if(head==NULL)return0;elsereturn(head-data+Sum(head-next));}一个典型的例子是在有序数组中查找一个数据元素是否存在的折半查找算法有序数组元素为1；3；4;5;17;18;31;33;寻找值为17的数据3.问题的求解方法是递归的第三种递归典型的三种情况使用递归：问题的定义是递归的数据结构是递归的问题求解的过程是递归的直接递归：函数直接调用本身。A(){……CALLA()......}间接递归：一函数在调用其他函数时，又产生了对自身的调用。A()B(){……{……CALLB（）CALLA（）……}……}二、递归分类递归模型是递归算法的抽象,它反映一个递归问题的递归结构,例如,前面的递归算法对应的递归模型如下：fun(1)=1(1)fun(n)=n*fun(n-1)n1(2)其中,第一个式子给出了递归的终止条件,第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系,第一个式子称为递归出口,第二个式子称为递归体。三、递归模型一般地,一个递归模型是由递归出口和递归体两部分组成,前者确定递归到何时结束,后者确定递归求解时的递推关系。实际上递归的思路是把一个不能或者不好直接求解的“大问题”转化为一个或者几个“小问题”来解决；再把“小问题”进一步分解为更小的“小问题”来解决；如此分解，直到“小问题”可以直接求解。递归模型的分解过程不是随意分解，分解问题规模要保证“大问题”和“小问题”的相似性，即求解过程和环境要具备相似性；一旦遇到递归出口，分解过程结束，开始求值，分解是量变的过程，大问题慢慢变小，但是尚未解决，遇到递归出口之后，发生了质变，即递归问题转化为直接问题。因此，递归算法的执行总是分为分解和求值两个部分。递归出口的一般格式如下f(s1)=m1递归体的一般格式f(sn)=g(f(sn-1),c)递归的分解过程递归求值的过程递归的求解的过程均有这样的特征：先将整个问题划分为若干个子问题,通过分别求解子问题,最后获得整个问题的解。而这些子问题具有与原问题相同的求解方法,于是可以再将它们划分成若干个子问题,分别求解,如此反复进行,直到不能再划分成子问题,或已经可以求解为止。这种自上而下将问题分解、求解,再自上而下引用、合并,求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。四、递归算法执行过程以阶乘的递归计算为例longFact(intn){longf;if(n0)printf(n0,inputerror);elseif(n==0||n==1)f=1;elsef=Fact(n-1)*n;return(f);}执行过程分析递归算法执行过程总结递归算法的执行过程是不断地自调用，直到到达递归出口才结束自调用过程；到达递归出口后，递归算法开始按最后调用的过程最先返回的次序返回；返回到最外层的调用语句时递归算法执行过程结束。五、递归算法的效率分析斐波那契数列Fib(n)的递归定义是：求第n项斐波那契数列的递归函数如下：longFib(intn){if(n==0||n==1)returnn;//递归出口elsereturnFib(n-1)+Fib(n-2);//递归调用}斐波那契数列计算的调用过程用归纳法可以证明求Fib(n)的递归调用次数等于2n-1；计算斐波那契数列的递归函数Fib(n)的时间复杂度为O(2n)。计算斐波那契数列Fib(n)问题，我们也可根据公式写出循环方式求解的函数如下：Fib(5)的递归调用树斐波那契数列的循环解决方案longFib2(intn){longintoneBack,twoBack,current;inti;if(n==0||n==1)returnn;else{oneBack=1;twoBack=0;for(i=2;i=n;i++){current=oneBack+twoBack;twoBack=oneBack;oneBack=current;}returncurrent;}}效率分析总结优点：----递归过程结构清晰----程序易读----正确性容易证明缺点：----时间效率低----空间开销大，问题规模扩大时，容易造成系统死机、瘫痪----算法不容易优化对于频繁使用的算法，或不具备递归功能的程序设计语言，需要把递归算法转换为非递归算法。六、递归算法的非递归化处理采用迭代算法（循环结构）尾递归的消除利用栈消除任何递归如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。比较常用的递归形式1.迭代法消除递归采用迭代算法longFact2(intn){∥用迭代算法求n!x=1;for(i=1;i=n;i++)x*=i;returnx;}∥Fact2递归从顶到底n!(n-1)!(n-2)!...2!1!0!迭代从底到顶将递归转换成迭代2.尾递归算法及其递归的消除voidOutput1(LinkedListL){∥顺序输出单链表结点数据的递归算法if(L){printf(L-data);∥输出结点的值Output1(L=L-next);∥尾递归调用}}∥Output1尾递归的消除-1：使用跳转语句voidOutput1(LinkedListL){∥顺序输出单链表结点数据的递归算法if(L){printf(L-data);∥输出结点的值Output1(L=L-next);∥尾递归调用}}∥Output1使用跳转语句voidOutput2(LinkedListL){∥顺序输出单链表结点数据的非递归算法1p=L;∥设局部变量p=LLbl:∥在第一个可执行语句前设标号if(p){printf(p-data);∥输出结点的值p=p-next;∥修改变量值gotoLb1;∥转到第一个可执行语句}}∥Output2尾递归的消除-2：使用循环语句voidOutput1(LinkedListL){∥顺序输出单链表结点数据的递归算法if(L){printf(L-data);∥输出结点的值Output1(L=L-next);∥尾递归调用}}∥Output1使用循环语句改造voidOutput3(LinkedListL){∥顺序输出单链表结点数据的非递归算法2p=L;∥设局部变量p=Lwhile(p){printf(p-data);∥输出结点的值p=p-next;∥向里一层修改变量值}}∥Output33.借助堆栈消除任何递归因为堆栈的后进先出特点正好和递归函数的运行特点相吻合。所以原理上讲，任何递归都可以转换为非递归的算法。利用栈可以将任何递归函数转换成非递归的形式，其步骤大致如下：具体步骤入栈处理在递归过程开始处，需要给局部变量赋值初始化栈，栈中每个记录包括函数的所有参数，如局部变量和返回地址。所有递归调用语句处，改写成把形参、局部变量和返回地址入栈的语句。确定、修改本次递归调用时的实参的新值。转到递归过程（函数）的开始处，即第一个语句。退栈处理在递归过程结束处，需要检测栈是否为空若栈空，算法结束，执行正常返回。若栈不空，从栈中退出参变量赋给原来入栈时相对应的参变量，并退出返回地址（出栈）。转到执行返回地址处的语句，继续执行。voidInOrder(BiTree*T){if(T){InOrder(T-lchild);visite(T);InOrder(T-rchild);}}#definemaxsize100中序遍历非递归算法typedefstruct{BitreeElem[maxsize];inttop;}SqStack;voidInOrderUnrec(Bitreet){SqStacks;StackInit(s);//初始化栈以保存调用过程（函数）的所有参数、局部变量和返回地址。p=t;//①递归过程开始前，给局部变量赋值while(p!=null||!StackEmpty(s))//若树不空或者栈不空，则执行，否则退出。{while(p!=null)//遍历左子树{push(s,p);//②递归调用语句处，改写成把形参、局部变量和返回地址入栈的语句。p=p-lchild;//③确定、修改本次递归调用时的实参值}//endwhileif(!StackEmpty(s))//④递归过程结束时，检测栈是否为空。若栈不空，从栈中退出参变量赋给原来入栈时相对应的参变量，并退出返回地址。{p=pop(s);visite(p-data);//⑤转到返回地址处执行，即访问根结点p=p-rchild;//⑥递归过程开始前，给局部变量赋值，通过下一次循环实现右子树遍历。}//endif}//endwhile}//InOrderUnrec利用堆栈消除递归的核心思想是模拟递归函数在执行的过程中，系统内部的进栈、退栈过程，需要对问题的处理非常熟悉，往往要具体问题具体对待，没有统一的的解决方案，因此上述给出的是原则性的转化方案。