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

主要内容主要内容什么时候使用递归什么时候使用递归递归分类递归分类递归模型递归模型递归算法的执行过程递归算法的执行过程递归算法的效率分析递归算法的效率分析递归算法的非递归化处理递归算法的非递归化处理一、什么时候使用递归？一、什么时候使用递归？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(n1)第一种递归阶乘的另外一种定义方法阶乘的另外一种定义方法有些数据结构是递归的。例如有些数据结构是递归的。例如,单链表就是一种递归数据结构单链表就是一种递归数据结构,其结点类型定义如其结点类型定义如下：下：typedef struct LNode ElemType data;struct LNode*next;LinkList;该定义中该定义中,结构体结构体LNode的定义中用到了它自身的定义中用到了它自身,即指即指针域针域next是一种指向自身类型的指针是一种指向自身类型的指针,所以它是一种递归所以它是一种递归数据结构。数据结构。2.数据结构是递归的数据结构是递归的第二种递归对对于于递递归归数数据据结结构构,采采用用递递归归的的方方法法编编写写算算法法既既方方便便又又有有效效。例例如如,求求一一个个不不带带头头结结点点的的单单链链表表head的的所有所有data域域(假设为假设为int型型)之和的递归算法如下：之和的递归算法如下：int Sum(LinkList*head)if(head=NULL)return 0;else return(head-data+Sum(head-next);一个典型的例子是在一个典型的例子是在有序数组中有序数组中查找一个数据元素是否存在的查找一个数据元素是否存在的折半折半查找算法查找算法有序数组元素有序数组元素为为1 1；3 3；4;5;17;18;31;4;5;17;18;31;33;33;寻找值为寻找值为1717的的数据数据3.问题的求解方法是递归的问题的求解方法是递归的第三种递归典型的三种情况使用递归：问题的定义是递归的数据结构是递归的问题求解的过程是递归的直接递归：直接递归：函数直接调用本身。函数直接调用本身。A()A()CALL A()CALL A().间接递归：间接递归：一函数在调用其他函数时，一函数在调用其他函数时，又产生了对自身的调用。又产生了对自身的调用。A()B()A()B()CALL B CALL B（）（）CALL ACALL A（）（）二、递归分类二、递归分类递递归归模模型型是是递递归归算算法法的的抽抽象象,它它反反映映一一个个递递归归问问题题的的递递归归结结构构,例例如如,前前面面的的递递归归算算法法对对应应的的递归模型如下：递归模型如下：fun(1)=1 (1)fun(n)=n*fun(n-1)n1 (2)其其中中,第第一一个个式式子子给给出出了了递递归归的的终终止止条条件件,第第二二个个式式子子给给出出了了fun(n)的的值值与与fun(n-1)的的值值之之间间的的关关系系,第第一一个个式式子子称称为为递递归归出出口口,第第二二个个式式子称为子称为递归体递归体。三、递归模型三、递归模型l一般地一般地,一个递归模型是由一个递归模型是由递归出口递归出口和和递归体递归体两部分两部分组成组成,前者确定递归到何时结束前者确定递归到何时结束,后者确定递归求解时后者确定递归求解时的递推关系。的递推关系。l实际上递归的思路是把一个不能或者不好直接求解的实际上递归的思路是把一个不能或者不好直接求解的“大问题大问题”转化为一个或者几个转化为一个或者几个“小问题小问题”来解决；来解决；l再把再把“小问题小问题”进一步分解为更小的进一步分解为更小的“小问题小问题”来解来解决；决；如此分解如此分解，直到，直到“小问题小问题”可以直接求解。可以直接求解。l递归模型的分解过程不是随意分解，分解问题规模要保证“大问题”和“小问题”的相似性，即求解过程和环境要具备相似性；l一旦遇到递归出口，分解过程结束，开始求值，分解是量变的过程，大问题慢慢变小，但是尚未解决，遇到递归遇到递归出口之后，发生了质变，即递归问题转化为直接问题。出口之后，发生了质变，即递归问题转化为直接问题。l因此，递归算法的执行总是分为分解和求值两个部分。l递归出口的一般格式如下递归出口的一般格式如下l f(s1)=m1l递归体的一般格式递归体的一般格式l f(sn)=g(f(sn-1),c)l递归的分解过程递归的分解过程l递归求值的过程递归求值的过程l递归的求解的过程均有这样的特征：递归的求解的过程均有这样的特征：l先将先将整个问题整个问题划分为若干个划分为若干个子问题子问题,通过分别通过分别求解子问题求解子问题,最后最后获得整个问题的解。而这些子问题具有与原问题相同的求解方获得整个问题的解。而这些子问题具有与原问题相同的求解方法法,于是可以再将它们划分成若干个子问题于是可以再将它们划分成若干个子问题,分别求解分别求解,如此反复如此反复进行进行,直到不能再划分成子问题直到不能再划分成子问题,或已经可以求解为止。或已经可以求解为止。l这种这种自上而下将问题分解、求解自上而下将问题分解、求解,再再自上而下引用、合并自上而下引用、合并,求出求出最后解答的过程称为最后解答的过程称为递归求解过程递归求解过程。这是一种。这是一种分而治之分而治之的算法的算法设计方法。设计方法。四、递归算法执行过程四、递归算法执行过程l以阶乘的递归计算为例llongFact(intn)llongf;lif(n0)printf(n0,inputerror);lelseif(n=0|n=1)f=1;lelsef=Fact(n-1)*n;lreturn(f);l执行过程分析执行过程分析递归算法执行过程总结递归算法执行过程总结u递归算法的执行过程是递归算法的执行过程是不断地自调用不断地自调用，直到到达递归出口才结束自调，直到到达递归出口才结束自调用过程；用过程；u到达递归出口后，递归算法开始按到达递归出口后，递归算法开始按最后调用的过程最先返回最后调用的过程最先返回的次序返的次序返回；回；u返回到最外层的调用语句时递归算法执行过程结束。返回到最外层的调用语句时递归算法执行过程结束。五、递归算法的效率分析五、递归算法的效率分析斐波那契数列斐波那契数列Fib(nFib(n)的递归定义是：的递归定义是：求第求第n n项斐波那契数列的项斐波那契数列的递归函数递归函数如下：如下：long Fib(int n)if(n=0|n=1)return n;/递归出口递归出口 else return Fib(n-1)+Fib(n-2);/递归调用递归调用斐波那契数列计算的调用过程斐波那契数列计算的调用过程 用归纳法可以证明求用归纳法可以证明求Fib(n)的递归的递归调用次数调用次数等于等于2n-1；计算斐波那契数列的递；计算斐波那契数列的递归函数归函数Fib(n)的的时间复杂度为时间复杂度为O(2n)。计算斐波那契数列。计算斐波那契数列Fib(n)问题，我们也可根问题，我们也可根据公式写出据公式写出循环方式求解的函数如下：循环方式求解的函数如下：Fib(5)Fib(5)的递归调用树的递归调用树 斐波那契数列的循环解决方案斐波那契数列的循环解决方案效率分析总结效率分析总结优点：-递归过程结构清晰-程序易读-正确性容易证明缺点：-时间效率低-空间开销大，问题规模扩大时，容易造成系统死机、瘫痪-算法不容易优化对于频繁使用的算法，或不具备递归功能的程序设计语言，需要把递递归算法转换为非递归算法归算法转换为非递归算法。六、递归算法的非递归化处理六、递归算法的非递归化处理l采用迭代算法（循环结构）l尾递归的消除l利用栈消除任何递归如果一个递归过程或递归如果一个递归过程或递归函数中递归调用语句是最函数中递归调用语句是最后一条执行语句后一条执行语句,则称这则称这种递归调用为种递归调用为尾递归尾递归。比。比较常用的递归形式较常用的递归形式1.迭代法消除递归迭代法消除递归采用迭代算法采用迭代算法long Fact2(int n)用迭代算法求n!x=1;for(i=1;idata);输出结点的值lOutput1(L=L-next);尾递归调用llOutput1尾递归的消除尾递归的消除-1：使用跳转语句：使用跳转语句lvoidOutput1(LinkedListL)l顺序输出单链表结点数据的递归算法lif(L)llprintf(L-data);输出结点的值lOutput1(L=L-next);尾递归调用llOutput1l使用跳转语句使用跳转语句voidOutput2(LinkedListL)l顺序输出单链表结点数据的非递归算法1lp=L;设局部变量p=LlLbl:在第一个可执行语句前设标号lif(p)printf(p-data);输出结点的值lp=p-next;修改变量值lgotoLb1;转到第一个可执行语句llOutput2尾递归的消除尾递归的消除-2：使用循环语句：使用循环语句lvoidOutput1(LinkedListL)l顺序输出单链表结点数据的递归算法lif(L)llprintf(L-data);输出结点的值lOutput1(L=L-next);尾递归调用llOutput1使用循环语句改造使用循环语句改造lvoidOutput3(LinkedListL)l顺序输出单链表结点数据的非递归算法2lp=L;设局部变量设局部变量p=Llwhile(p)lprintf(p-data);输出结点的值lp=p-next;向里一层修改变量值llOutput33.借助堆栈消除任何递归借助堆栈消除任何递归l因为堆栈的后进先出特点正好和递归函数的运行特点相吻因为堆栈的后进先出特点正好和递归函数的运行特点相吻合。所以原理上讲，任何递归都可以转换为非递归的算法。合。所以原理上讲，任何递归都可以转换为非递归的算法。l利用栈可以将任何递归函数转换成非递归的形式，其步骤利用栈可以将任何递归函数转换成非递归的形式，其步骤大致如下：大致如下：具体步骤具体步骤l入栈处理入栈处理在递归过程开始处，需要给局部变量赋值在递归过程开始处，需要给局部变量赋值l初始化栈，栈中每个记录包括函数的所有参数，如局部变量和返回地初始化栈，栈中每个记录包括函数的所有参数，如局部变量和返回地址。址。l所有递归调用语句处，改写成把形参、局部变量和返回地址所有递归调用语句处，改写成把形参、局部变量和返回地址入入栈栈的语句。的语句。l确定、修改本次递归调用时的实参的新值。确定、修改本次递归调用时的实参的新值。l转到递归过程（函数）的开始处，即第一个语句。转到递归过程（函数）的开始处，即第一个语句。l退栈处理退栈处理在递归过程结束处，需要检测栈是否为空在递归过程结束处，需要检测栈是否为空l若栈空，算法结束，执行正常返回。若栈空，算法结束，执行正常返回。l若栈不空，从栈中退出参变量赋给原来入栈时相对应的参变量，若栈不空，从栈中退出参变量赋给原来入栈时相对应的参变量，并退出返回地址（出栈）。并退出返回地址（出栈）。l转到执行返回地址处的语句，继续执行。转到执行返回地址处的语句，继续执行。l lvoidvoidInOrderInOrder(BiTreeBiTree*T)*T)l lif(T)if(T)l ll lInOrderInOrder(T-(T-lchildlchild););visitevisite(T);(T);InOrderInOrder(T-(T-rchildrchild););l ll ll l#define#definemaxsizemaxsize100100中序遍历非递归算法中序遍历非递归算法l ltypedeftypedef structstruct l l BitreeBitree ElemmaxsizeElemmaxsize;l lintinttop;top;l l SqStackSqStack;l lvoidvoidInOrderUnrec(BitreeInOrderUnrec(Bitreet)t)l l SqStackSqStacks;s;l l StackInit(sStackInit(s););/初始化栈以保存调用过程（函数）的所有参数、局部变量和返回地址。初始化栈以保存调用过程（函数）的所有参数、局部变量和返回地址。l lp=t;p=t;/递归过程开始前，给局部变量赋值递归过程开始前，给局部变量赋值递归过程开始前，给局部变量赋值递归过程开始前，给局部变量赋值l l while(p!=null|!while(p!=null|!StackEmpty(sStackEmpty(s)/若树不空或者栈不空，则执行，否则退出。若树不空或者栈不空，则执行，否则退出。l ll l while(p!=null)/遍历左子树遍历左子树llpush(s,p);/递归调用语句处，改写成把形参、局部变量和返回地址入栈的语句。递归调用语句处，改写成把形参、局部变量和返回地址入栈的语句。lp=p-lchild;/确定、修改本次递归调用时的实参值确定、修改本次递归调用时的实参值l/endwhilelif(!StackEmpty(s)/递归过程结束时，检测栈是否为空。若栈不空，从栈中退出参变量赋给原来入递归过程结束时，检测栈是否为空。若栈不空，从栈中退出参变量赋给原来入栈时相对应的参变量，并退出返回地址。栈时相对应的参变量，并退出返回地址。lp=pop(s);lvisite(p-data);/转到返回地址处执行，即访问根结点转到返回地址处执行，即访问根结点lp=p-rchild;/递归过程开始前，给局部变量赋值，通过下一次循环实现右子树遍历递归过程开始前，给局部变量赋值，通过下一次循环实现右子树遍历。l/endifl/endwhileendwhile/InOrderUnrec 利用堆栈消除递归的核心思想是模拟递归函数利用堆栈消除递归的核心思想是模拟递归函数在执行的过程中，系统内部的进栈、退栈过程，需在执行的过程中，系统内部的进栈、退栈过程，需要对问题的处理非常熟悉，往往要具体问题具体对要对问题的处理非常熟悉，往往要具体问题具体对待，没有统一的的解决方案，因此上述给出的是原待，没有统一的的解决方案，因此上述给出的是原则性的转化方案。则性的转化方案。