《递归算法梁.ppt》由会员分享，可在线阅读，更多相关《递归算法梁.ppt（30页珍藏版）》请在三一文库上搜索。
1、第6章 递归算法,主讲：梁宝兰,2,第 6 章 递归算法,主要内容：,递归的概念 递归算法的执行过程 递归算法的设计方法 递归过程和运行时栈 递归算法的效率分析 递归算法到非递归算法的转换,3,递归算法 直接或间接调用自身的算法称为递归算法 1、问题的定义是递归的 例：阶乘函数定义,6.1 递归的概念,4,2、问题的解法存在自调用 例：在有序数组a中查找是否存在元素x。 二分查找思想： 在alowahight(low为寻找区域中开始处下标，high则为结束处的下标)寻找是否存在元素x； 若lowhigh,则不存在x，返回-1； 否则，求出中间元素下标mid=(low+high)/2； 若ami
2、d=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
3、=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,l
4、ow,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的阶乘递归函数执行过程,保护现场,保护现场,保护现场,保护现场,恢复现场,
5、恢复现场,恢复现场,恢复现场,6.2 递归算法的执行过程,10,函数调用的现场保护与现场恢复： 1) 当前指令地址 在转到被调用函数前，保存当前主调函数执行的指令地址； 当被调用函数执行完毕后，按照栈顶中所保存的指令地址，转至该指令处继续往下执行。 2) 本函数的局部变量值。 在转到被调用函数前，保存当前主调函数的局部标量；当函数调用返回时，根据栈中队局部变量的值恢复主调函数的局部变量。,6.2 递归算法的执行过程,11,12,根据栈中内容，恢复fact(1)现场,根据栈中内容，恢复fact(2)现场,根据栈中内容，恢复fact(3)现场,根据栈中内容，恢复main()现场,返回地址,1,返回
6、地址,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),算法分析：小人只能向上或向右前进，则小人需
7、要到达目的地，可以分为以下情况：,如果：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; else return r
8、oad1(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、自己用堆栈模拟系统的运行时的栈，通过分析只保存必须保存的信
9、息，从而用非递归算法替代递归算法(略) 。,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
10、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 设计一个输出如下形式数值的递
11、归算法。 n n n . n 3 3 3 2 2 1 问题分析：该问题可以看成由两部分组成：一部分是输出一行值为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)个人组成一个委员会，计算共有多少种构成方法。 递归算法分析：
12、设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,