2-2-递归与非递归程序的转换(精品).ppt
递归程序递归程序非递归程序非递归程序张仕0 递归的基本概念递归的基本概念l递归：在定义一个过程或函数时，如果出现调用本过程或本函数的成分，则称为递归。l直接递归：在定义一个过程或函数时，出现直接调用本过程或本函数成分的情况。l直接递归：在定义一个过程或函数时，出现间接调用本过程或本函数成分的情况。0 递归的基本概念递归的基本概念function_1(X)if(X)X*function_1(X-1);else return;Function_1、function_2实现了什么功能？还有哪些常见的递归函数？function_2(X)if(X)function_3(X);else return;function_3(X)return X*function_2(X-1);0 递归的基本概念递归的基本概念l在什么情况下用到递归方法给出的定义是递归的：许多数学公式、数列的定义是递归的，这是可以直接把递归定义转换为递归算法：例如Fabonacci数列。数据结构是递归的：常见的有树、链表等数据结构的定义。对于这类数据结构，常采用递归的方法进行操作。例如链表的遍历、树的遍历操作。问题求解的方法是递归的。例如汉诺塔问题，其求解方法是递归的。1 递归算法的设计递归算法的设计l递归模型：递归模型是递归算法的抽象,它反映递归问题的递归结构,例如,前面的递归算法对应的递归模型如下：fun(0)=1 n=0(1)fun(n)=n*fun(n-1)n0(2)其中：第一个式子给出了递归的终止条件,我们称之为递归出口；第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系，我们称之为递归体。1 递归算法的设计递归算法的设计l一般地,一个递归模型是由递归出口和递归体两部分组成,前者确定递归到何时结束,后者确定递归求解时的递推关系。递归出口的一般格式如下：f(s1)=m1这里的s1与m1均为常量,有些递归问题可能有几个递归出口。1 递归算法的设计递归算法的设计l递归体的一般格式如下：f(sn+1)=g(f(si),f(si+1),f(sn),cj,cj+1,cm)其中,n,i,j,m均为正整数。sn+1是一个递归“大问题”,si,si+1,sn为递归“小问题”,cj,cj+1,cm是可以用非递归方法直接解决的问题 g是一个非递归函数,可以直接求值。1 递归算法的设计递归算法的设计l递归思路实际上，递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决(此时分解到递归出口)。但递归分解不是随意的分解，递归分解要保证“大问题”与“小问题”相似，即求解过程与环境都相似。并且有一个分解的终点。从而使问题可解。1 递归算法的设计递归算法的设计逐步分解和组合求值的过程1 递归算法的设计递归算法的设计l斐波那契数：一个大问题分解为多个小问题的过程1 递归算法的设计递归算法的设计l算法设计：先将整个问题划分为若干个子问题，通过分别求解子问题，最后获得整个问题的解。而这些子问题具有与原问题相同的求解方法，于是可以再将它们划分成若干个子问题，分别求解，如此反复进行，直到不能再划分成子问题，或已经可以求解为止。这种自上而下将问题分解、求解，再自上而下引用、合并，求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。1 递归算法的设计递归算法的设计l递归设计的步骤如下：(1)对原问题f(s)进行分析,假设出合理的“较小问题”f(s)(与数学归纳法中假设n=k-1时等式成立相似)；(2)假设f(s)是可解的,在此基础上确定f(s)的解,即给出f(s)与f(s)之间的关系(与数学归纳法中求证n=k时等式成立的过程相似)；(3)确定一个特定情况(如f(1)或f(0)的解,由此作为递归出口(与数学归纳法中求证n=1时等式成立相似)。1 递归算法的设计递归算法的设计l课堂练习：采用递归算法求实数数组A0.n-1中的最小值。基本步骤：l先定义清楚问题；l写出递归模型；l转换为算法。2 为什么：递归为什么：递归非递归？非递归？l引例求如下函数值 Sum(1.X)=X+Sum(1.X-1)X0 Sum(1.X)=0 X=0它的程序？2 为什么：递归为什么：递归非递归？非递归？l利用递归求该函数#include stdafx.h#include using namespace std;int _tmain(int argc,_TCHAR*argv)coutadd(5000);return 0;int add(int x)if(x=0)return 0;return x+add(x-1);2 为什么：递归为什么：递归非递归？非递归？l利用非递归(迭代)求该函数#include stdafx.h#include using namespace std;int _tmain(int argc,_TCHAR*argv)cout0;i-)result+=x;return result;2 为什么：递归为什么：递归非递归？非递归？l它们的运行结果？递归 迭代X=10 X=100X=1000X=10000X=100000 l为什么？2 为什么：递归为什么：递归非递归？非递归？l利用递归求该函数#include stdafx.h#include using namespace std;int _tmain(int argc,_TCHAR*argv)coutadd(5000);return 0;int add(int x)char a1000;if(x=2讨论直接使用栈保存中间结果，从而将递归算法转化为非递归算法的过程。以求N!为例,其递归模型有一个递归体和一个递归出口两个式子,分别称为(1)式和(2)式。3 递归递归非递归的非递归的转换方法方法1-表述表述2设计一个栈,其结构如下：struct int vn;/*保存n值*/int vf;/*保存fun1(n)值*/int tag;/*标识是否求出fun1(n)值,1:未求出,0:已求出*/StMaxSize;/*定义简单数组栈*/3 递归递归非递归的非递归的转换方法方法1-表述表述2计算fun1(5)之值的过程如下：将(5,*,1)进栈;while(栈不空)if(未计算出栈顶元素的vf值即Sttop.tag=1)if(栈顶元素满足(1)式)求出对应的Sttop.vf值,置Sttop.tag=0;else /*栈顶元素满足(2)式*/将(Sttop.vn-1,*,1)进栈;else if(已计算出栈顶元素的vf值即Sttop.tag=0)显然栈顶元素由次栈顶元素通过(2)式分解得到的，回过来 由栈顶元素的vf值计算出次栈顶元素的vf值并退栈;if (栈中只有一个已求出vf值的元素)退出循环;St0.vf即为所求的fun1(n)值;3 递归递归非递归的转换方法非递归的转换方法1-表述表述23 递归递归非递归的转换方法非递归的转换方法1-表述表述2 对应的非递归fun1算法如下：int fun1(int n)top+;/*初值进栈*/Sttop.vn=n;Sttop.tag=1;while(top-1)/*栈不空时循环*/if(Sttop.tag=1)/*未计算出栈顶元素的vf值*/if(Sttop.vn=0)/*(1)式*/Sttop.vf=1;Sttop.tag=0;else/*(2)式*/top+;Sttop.vn=Sttop-1.vn-1;Sttop.tag=1;3 递归递归非递归的转换方法非递归的转换方法1-表述表述2else if(Sttop.tag=0)/*已计算出vf值*/Sttop-1.vf=Sttop-1.vn*Sttop.vf;/*(2)式*/Sttop-1.tag=0;top-;/*栈中只有一个已求出vf的元素时退出循环*/if(top=0&Sttop.tag=0)break;return(Sttop.vf);3 递归递归非递归的转换方法非递归的转换方法1-表述表述2l练习以N=5为例，完整的在纸上模拟整个算法的运算过程，以此加深对表述2的理解。以表述2方法，求斐波那契数的栈模拟递归算法。其中，斐波那契数（Fobanacci）定义如下：lf(1)=1lf(2)=1lf(n)=f(n-1)+f(n-2),其中n=23 递归递归非递归的转换方法非递归的转换方法2l利用栈保存参数：该方法通常以栈为保存运行中间数据的媒介。l例：二叉树的中序遍历。DFS(T)lDFS(T-lchild);lVisit(T);lDFS(T-rchild);3 递归递归非递归的转换方法非递归的转换方法2Status InOrder(BiTree root,Status(*Visit)(ElemType e)/*中序遍历二叉树,root指向二叉树(或某一子树)*/if(root!=NULL)if(InOrder(root-LChild,visit)/*遍历左子树*/if(Visit(root-data)/*访问根结点*/if(InOrder(root-RChild,visit)/*遍历右子树*/return OK;return Error;else return OK;3 递归递归非递归的转换方法非递归的转换方法2利用栈来模拟整个遍历过程，再根据遍历写出算法。3 递归递归非递归的转换方法非递归的转换方法2void InOrder（BiTree root）/*中序遍历二叉树的非递归算法*/InitStack(S);p=root;while(p!=NULL|!IsEmpty(S)if(p!=NULL)/*根指针进栈，遍历左子树*/Push(S,p);p=p-LChild;else/*根指针退栈，访问根结点，遍历右子树*/Pop(S,p);Visit(p-data);p=p-RChild;/end of while 3 递归递归非递归的转换方法非递归的转换方法3l利用迭代消除递归：通过分析，跳过分解过程，直接用循环结构的算法实现求值过程。l斐波那契数（Fobanacci）定义如下：f(1)=1f(2)=1f(n)=f(n-1)+f(n-2),其中n=2从中找出循环求值。3 递归递归非递归的转换方法非递归的转换方法3求解Fibonacci数列的算法如下：int Fib(int n)int i,f1,f2,f3;if(n=1|n=2)return(n);f1=1;f2=2;for(i=3;i=n;i+)f3=f1+f2;f1=f2;f2=f3;return(f3);3 递归递归非递归的转换方法非递归的转换方法3l利用迭代求解的难点：要很好地理解整个算法的思想，然后重新设计一个合理的迭代过程。0-1背包问题背包问题l 0-1背包问题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。价值 体积3 递归递归非递归的转换方法非递归的转换方法3建立模型分析：定义m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。可以建立计算m(i，j)的递归式如下。3 递归递归非递归的转换方法非递归的转换方法3没有物品时l练习：1 理解0-1背包问题求解的基本思想；2 按照上述分析结果写出递归算法；3 通过对下例求解过程模拟，理解算法求解过程；n=5，c=10 w=2，2，6，5，4，v=6，3，5，4，6。4 把递归算法改写为迭代算法。4 小结小结l本章基本学习要点如下：本章基本学习要点如下：(1)(1)理解递归的定义和递归模型。理解递归的定义和递归模型。(2)(2)重点掌握递归的执行过程。重点掌握递归的执行过程。(3)(3)掌握递归设计的一般方法。掌握递归设计的一般方法。(4)(4)掌握消除递归的基本方法。掌握消除递归的基本方法。(5)(5)灵活运用递归算法解决一些较复杂应用问题。灵活运用递归算法解决一些较复杂应用问题。
