《递归算法梁》PPT课件.ppt
第6章递归算法,主讲：梁宝兰,2,第 6 章 递归算法,主要内容：,递归的概念递归算法的执行过程递归算法的设计方法递归过程和运行时栈递归算法的效率分析递归算法到非递归算法的转换,3,递归算法 直接或间接调用自身的算法称为递归算法1、问题的定义是递归的 例：阶乘函数定义,6.1 递归的概念,4,2、问题的解法存在自调用例：在有序数组a中查找是否存在元素x。二分查找思想：在alowahight(low为寻找区域中开始处下标，high则为结束处的下标)寻找是否存在元素x；若lowhigh,则不存在x，返回-1；否则，求出中间元素下标mid=(low+high)/2；若amid=x，则查找成功返回mid的值；若amidx则在alowamid-1间继续寻找；若amidx则在amid+1ahigh间继续寻找；,6.1 递归的概念,5,在有序表中查找21：,第一次比较：low=0，high=10，mid=5；amid21;则high=mid-1=4，并在alowahigh中继续查找；,第二次比较：low=0，high=4，mid=2；amid21;则low=mid+1=3，并在alowahigh中继续查找；,第三次比较：low=3，high=4，mid=3；amid=21;则返回mid的值；,6,在有序表中查找20：,第一次比较：low=0，high=10，mid=5；amid20;则high=mid-1=4，并在alowahigh中继续查找；,第二次比较：low=0，high=4，mid=2；amid20;则low=mid+1=3，并在alowahigh中继续查找；,第三次比较：low=3，high=4，mid=3；amid20;则high=mid-1=2，并在alowahigh中继续查找；,第四次比较：lowhigh,20不存在数组中，返回-1；,7,/算法实现int bin_search(node r,int low,int high,ElemType k)int mid;if(lowk)return bin_search(r,low,mid-1,k);/左 else return bin_search(r,mid-1,high,k);/右,6.1 递归的概念,8,6.2 递归算法的执行过程,/求阶乘的递归程序int fact(int n)int x,y;if(n0)cout“error!”endl;return-1;if(n=0)return 1;else x=n-1;y=fact(x);return n*y;void main()int fn;fn=fact(3);coutfnendl;,9,n=3的阶乘递归函数执行过程,保护现场,保护现场,保护现场,保护现场,恢复现场,恢复现场,恢复现场,恢复现场,6.2 递归算法的执行过程,10,函数调用的现场保护与现场恢复：1)当前指令地址 在转到被调用函数前，保存当前主调函数执行的指令地址；当被调用函数执行完毕后，按照栈顶中所保存的指令地址，转至该指令处继续往下执行。2)本函数的局部变量值。在转到被调用函数前，保存当前主调函数的局部标量；当函数调用返回时，根据栈中队局部变量的值恢复主调函数的局部变量。,6.2 递归算法的执行过程,11,12,根据栈中内容，恢复fact(1)现场,根据栈中内容，恢复fact(2)现场,根据栈中内容，恢复fact(3)现场,根据栈中内容，恢复main()现场,返回地址,1,返回地址,1,返回地址,2,6,返回地址,13,6.3 递归算法的设计方法,用递归算法求解问题的充分必要条件:1.问题具有某种可借用的类同自身的子问题描述的性质 2.某一有限步的子问题有直接的解存在设计递归算法的方法:1.把对原问题的求解设计成对子问题求解的形式 2.设计递归的出口,14,田字表中路径数,如下图所示，田字表由m*n个1*1的方格所组成，在田字表右下角原点处（0,0）处有一小人，该小人需要可以沿着表中框线向上或向右前进。则小人从原点出发，到达（m，n）定点可以有多少中走法。,(0,0),(m,n),15,(0,0),(m,n),算法分析：小人只能向上或向右前进，则小人需要到达目的地，可以分为以下情况：,如果：m=0，只有直线向上的走法；n=0，则只有直线向右的走法。否则：m,n0则有两种选择到达目的地：(1)从(m,n-1)向上走一步到达(2)从(m-1,n)向右走一步到达,16,/计算从原点到达(m,n)的走法数int road(int m,int n)如果 m=0 或n=0；返回1；/递归出口 否则 返回 road(m-1,n)+road(m,n-1);,田字表中路径数函数,17,/计算从原点到达(m,n)的走法数int road(int m,int n)if(m=0|n=0)return 1;elsereturn road1(m,n-1)+road1(m-1,n);void main()int m,n;cinmn;cout路径总数：road(m,n);endl;,18,6.5 递归算法的效率分析,递归算法的优点：结构清晰，可读性强，容易用数学归纳法来证明算法的正确性。递归算法的缺点：递归算法，需要多次调用自身，在调用函数时，现场保护以及恢复现场消耗时间与空间；且递归算法，往往不能利用已经求解过得问题的解，导致重复计算，消耗时间。,19,6.6 消除递归,递归算法转化为非递归算法有两种基本方法：1、可用循环结构进行递推。2、自己用堆栈模拟系统的运行时的栈，通过分析只保存必须保存的信息，从而用非递归算法替代递归算法(略)。,20,一、用循环结构的算法消除,如：阶乘问题的递归算法Fact(n),long fact2(int n)int fac=1;for(inti=1;i=n;i+)fac=fac*i;return fac;,long fact1(int n)if(n=0)return 1;return n*fact1(n-1);,21,/二分查找法算法的非递归实现int bin_search(int a,int low,int high,int k)int mid;while(lowk)hig=mid-1;/在左子区间中查找 else low=mid+1;/在右子区间中查找 return(-1);,一、用循环结构的算法消除,22,/利用二维数组进行递推求解田字表中路径数函数int road(int m,int n)int rMaxMMaxN,count=0;for(int x=0;x=m;x+)rx0=1;for(int y=0;y=n;y+)r0y=1;for(x=1;x=m;x+)for(y=1;y=n;y+)rxy=rx-1y+rxy-1;return rmn;,一、用循环结构的算法消除,23,6.7 设计举例,6.7.1 一般递归算法设计举例,例6-5 设计一个输出如下形式数值的递归算法。n n n.n.3 3 3 2 21问题分析：该问题可以看成由两部分组成：一部分是输出一行值为n的数值；另一部分是原问题的子问题，其参数为n-1。当参数减到0时不再输出任何数据值，因此递归的出口是当参数n0时空语句返回。,24,/算法设计：递归算法设计如下：void Display(int n)int i;for(i=1;i 0)Display(n-1);/递归，n=0为递归出口,6.7 设计举例,25,例6-6 设计求解委员会问题的算法。委员会问题是：从一个有n个人的团体中选举k(kn)个人组成一个委员会，计算共有多少种构成方法。递归算法分析：设n个人分别为P(1)，P(2)P(n-1)，P(n)若：n=k或k=0则构成方法只有1种否则：k1且nk,则P(1)要么在委员会中，要么不在，则；当P(1)在委员中时，则需要在P(2)P(n)中选举k-1个人当P(1)在委员中时，则需要在P(2)P(n)中选举k个人,委员会选举,26,委员会选举,27,委员会选举,/委员会选举函数int comm(n,k)/在n个人种选举k个委员的方法数 if(n=k|k=0)return 1;else return comn(n-1,k-1)+comnn(n-1,k);,28,作业9 10 11 12（1）,29,本章实验,利用非递归算法求解委员会选举问题。,The End,
