专题讲座--非递归化(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；3；4;5;17;18;31;33; 寻找值为17的数据,3. 问题的求解方法是递归的,第三种递归,典型的三种情况使用递归： 问题的定义是递归的 数据结构是递归的 问题求解的过程是递归的,直接递归：函数直接调用本身。 A( ) CALL A( ) 间接递归：一函数在调用其他函数时，又产生了对自身的调用。 A( ) B( ) CALL B（） CALL A（） ,二、递归分类,递归模型是递归算法的抽象,它反映一个递归问题的递归结构,例如,前面的递归算法对应的递归模型如下： 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) 递归的分解过程 递归求值的过程,递归的求解的过程均有这样的特征： 先将整个问题划分为若干个子问题,通过分别求解子问题,最后获得整个问题的解。而这些子问题具有与原问题相同的求解方法,于是可以再将它们划分成若干个子问题,分别求解,如此反复进行,直到不能再划分成子问题,或已经可以求解为止。 这种自上而下将问题分解、求解,再自上而下引用、合并,求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。,四、递归算法执行过程,以阶乘的递归计算为例 long Fact(int n) long f; if(n0) printf(“n0,input error“); else if(n=0|n=1) f=1; else f=Fact (n-1)*n; return(f); ,执行过程分析,递归算法执行过程总结,递归算法的执行过程是不断地自调用，直到到达递归出口才结束自调用过程； 到达递归出口后，递归算法开始按最后调用的过程最先返回的次序返回； 返回到最外层的调用语句时递归算法执行过程结束。,五、递归算法的效率分析,斐波那契数列Fib(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)的递归调用树,斐波那契数列的循环解决方案,效率分析总结,优点：-递归过程结构清晰 -程序易读 -正确性容易证明 缺点：-时间效率低 -空间开销大，问题规模扩大时，容易造成系统死机、瘫痪 -算法不容易优化 对于频繁使用的算法，或不具备递归功能的程序设计语言，需要把递归算法转换为非递归算法。,六、递归算法的非递归化处理,采用迭代算法（循环结构） 尾递归的消除 利用栈消除任何递归,如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。比较常用的递归形式,1.迭代法消除递归,采用迭代算法,long Fact2(int n) 用迭代算法求n! x=1; for(i=1;i=n;i+) x*=i; return x; Fact2,2.尾递归算法及其递归的消除,void Output1(LinkedList L) 顺序输出单链表结点数据的递归算法 if(L) printf(L-data); 输出结点的值 Output1(L=L-next); 尾递归调用 Output1,尾递归的消除-1：使用跳转语句,void Output1(LinkedList L) 顺序输出单链表结点数据的递归算法 if(L) printf(L-data); 输出结点的值 Output1(L=L-next); 尾递归调用 Output1 使用跳转语句 void Output2(LinkedList L) 顺序输出单链表结点数据的非递归算法1 p=L; 设局部变量p=L Lbl: 在第一个可执行语句前设标号 if(p)printf(p-data);输出结点的值 p=p-next; 修改变量值 goto Lb1; 转到第一个可执行语句 Output2,尾递归的消除-2：使用循环语句,void Output1(LinkedList L) 顺序输出单链表结点数据的递归算法 if(L) printf(L-data); 输出结点的值 Output1(L=L-next); 尾递归调用 Output1 使用循环语句改造 void Output3(LinkedList L) 顺序输出单链表结点数据的非递归算法2 p=L; 设局部变量p=L while(p) printf(p-data); 输出结点的值 p=p-next; 向里一层修改变量值 Output3,3.借助堆栈消除任何递归,因为堆栈的后进先出特点正好和递归函数的运行特点相吻合。所以原理上讲，任何递归都可以转换为非递归的算法。 利用栈可以将任何递归函数转换成非递归的形式，其步骤大致如下：,具体步骤,入栈处理 在递归过程开始处，需要给局部变量赋值 初始化栈，栈中每个记录包括函数的所有参数，如局部变量和返回地址。 所有递归调用语句处，改写成把形参、局部变量和返回地址入栈的语句。 确定、修改本次递归调用时的实参的新值。 转到递归过程（函数）的开始处，即第一个语句。 退栈处理 在递归过程结束处，需要检测栈是否为空 若栈空，算法结束，执行正常返回。 若栈不空，从栈中退出参变量赋给原来入栈时相对应的参变量，并退出返回地址（出栈）。 转到执行返回地址处的语句，继续执行。,void InOrder ( BiTree *T) if ( T ) InOrder ( T-lchild ) ; visite ( T ); InOrder ( T-rchild ) ; #define maxsize 100 中序遍历非递归算法 typedef struct Bitree Elemmaxsize; int top; SqStack; void InOrderUnrec(Bitree t) SqStack s; 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);