第06章 指针.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第,6章 递归算法,递归的概念,递归算法的执行过程,递归算法的设计方法,递归过程和运行时栈,递归算法的效率分析,递归算法到非递归算法的转换,设计举例,主要知识点,1,存在算法调用自己的情况：,若一个算法直接的或间接的,调用自己本身,，则称这个算法是递归算法。,（1）问题的定义是递推的,阶乘,函数的,常见定义,是：,6.1递归的概念,2,也可,定义为：,写成,函数形式，则为：,这种函数定义的方法是,用阶乘函数自己本身定义了阶乘函数，,称公式（6 3）是阶乘函数的,递推定义式,。,3,（,2）问题的解法存在自调用,一个典型的例子是在,有序数组中,查找一个数据元素是否存在的,折半查找算法,。,图,6-1,折半查找过程,4,6.2递归算法的执行过程,例6-1 给出按照公式6-3计算阶乘函数的递归算法，并给出,n=3,时递归算法的执行过程。,设计：按照公式,6-3,计算阶乘函数的递归算法如下：,long,int,Fact(,int,n),int,x;,long,int,y;,if(n 0),/n high)return-1;/,查找不成功,mid=(low+high)/2;,if(x=amid)return mid;/,查找成功,else if(x amid),return,BSearch,(a,x,low,mid-1);/,在下半区查找,else,return,BSearch,(a,x,mid+1,high);/,在上半区查找,例6-2 给出在有序数组,a,中查找数据元素,x,是否存在的递归算法，并给出如图6-1所示实际数据的递归算法的执行过程。递归算法如下：,8,测试主函数设计如下：,#,include,main(void),int,a=1,3,4,5,17,18,31,33;,int,x=17;,int bn,;,bn,=,BSearch,(a,x,0,7);,if(,bn,=-1),printf,(x,不在数组,a,中);,else,printf,(x,在数组,a,的下标%,d中,bn,);,9,BSearch,(a,x,0,7),的递归调用过程如图,6-3,所示，其中，,实箭头表示函数调用，虚箭头表示函数的返回值,。,图,6-3,BSearch,(a,x,0,7),的递归调用过程,10,6.3递归算法的设计方法,递归算法既是一种有效的算法设计方法，也是一种有效的分析问题的方法。递归算法求解问题的,基本思想是：,对于一个较为复杂的问题，把,原问题分解成若干个相对简单且类同的子问题,这样，原问题就可递推得到解。,适宜于用递归算法求解的问题的,充分必要条件是：,（1）问题具有某种可借用的类同自身的子问题描述的性质；,（2）某一有限步的子问题（也称作本原问题）有直接的解存在。,当一个问题存在上述两个基本要素时，该问题的,递归算法的设计方法是：,（1）把对原问题的求解设计成包含有对子问题求解的形式。,（2）设计递归出口。,11,例6-3 设计模拟,汉诺塔问题,求解过程的算法。汉诺塔问题的描述是：设有3根标号为,A，B，C,的柱子，在,A,柱上放着,n,个盘子，每一个都比下面的略小一点，要求把,A,柱上的盘子全部移到,C,柱上，移动的规则是：（1）一次只能移动一个盘子；（2）移动过程中大盘子不能放在小盘子上面；（3）在移动过程中盘子可以放在,A，B，C,的任意一个柱子上。,问题分析,：,可以用递归方法求解,n,个盘子的汉诺塔问题。,基本思想,：,1,个盘子的汉诺塔问题可直接移动。,n,个盘子的汉诺塔问题可递归表示为，首先把上边的,n-1,个盘子从,A,柱移到,B,柱，然后把最下边的一个盘子从,A,柱移到,C,柱，最后把移到,B,柱的,n-1,个盘子再移到,C,柱。,4,个盘子汉诺塔问题的递归求解示意图如图,6-4,所示。,12,图,6-4,汉诺塔问题的递归求解示意图,13,算法设计：,首先，盘子的个数,n,是必须的一个输入参数，对,n,个盘子,我们可从上至下依次编号为1,2,n；,其次，输入参数还需有3个柱子的代号,我们令3个柱子的参数名分别为,fromPeg,，,auxPeg,和,toPeg,；,最后，汉诺塔问题的求解是一个处理过程，因此算法的输出是,n,个盘子从柱子,fromPeg,借助柱子,auxPeg,移动到柱子,toPeg,的移动步骤，我们设计每一步的移动为屏幕显示如下形式的信息：,Move Disk i from Peg X to Peg Y,这样，汉诺塔问题的,递归算法可设计如下：,14,void towers(,int,n,char,fromPeg,char,toPeg,char,auxPeg,),if(n=1),/,递归出口,printf,(%s%c%s%cn,move disk 1 from peg,fromPeg,to peg,toPeg,);,return;,/,把,n-1,个圆盘从,fromPeg,借助,toPeg,移至,auxPeg,towers(n-1,fromPeg,auxPeg,toPeg,);,/,把圆盘,n,由,fromPeg,直接移至,toPeg,printf,(%s%d%s%c%s%cn,move disk,n,from peg,fromPeg,to peg,toPeg,);,/,把,n-1,个圆盘从,auxPeg,借助,fromPeg,移至,toPeg,towers(n-1,auxPeg,toPeg,fromPeg,);,15,测试主函数如下：,#,include,void main(void),Towers(4,A,C,B);,程序运行的输出信息如下：,16,Move Disk,1from Peg,A,to Peg,B,Move Disk,2,from Peg,A,to Peg,C,Move Disk,1,from Peg,B,to Peg,C,Move Disk,3,from Peg,A,to Peg,B,Move Disk,1,from Peg,C,to Peg,A,Move Disk,2,from Peg,C,to Peg,B,Move Disk,1,from Peg,A,to Peg,B,Move Disk,4,from Peg,A,to Peg,C,Move Disk,1,from Peg,B,to Peg,C,Move Disk,2,from Peg,B,to Peg,A,Move Disk,1,from Peg,C,to Peg,A,Move Disk,3,from Peg,B,to Peg,C,Move Disk,1,from Peg,A,to Peg,B,Move Disk,2,from Peg,A,to Peg,C,Move Disk,1,from Peg,B,to Peg,C,17,总结如下：,递归算法的执行过程是,不断地自调用,，直到到达递归出口才结束自调用过程；到达递归出口后，递归算法开始按,最后调用的过程最先返回,的次序返回；返回到最外层的调用语句时递归算法执行过程结束,。,18,6.4,递归过程和运行时栈,对于非递归函数，调用函数在调用被调用函数前，系统要,保存,以下两类,信息,：,（1）调用函数的返回地址；,（2）调用函数的局部变量值。,当执行完被调用函数，返回调用函数前，系统首先要,恢复,调用函数的,局部变量值,，然后,返回,调用函数的,返回地址,。,递归函数被调用时，系统要作的工作和非递归函数被调用时系统要作的工作在,形式上类同,，但,保存信息的方法不同,。,递归函数被调用时，系统的运行时栈也要保存上述两类信息。每一层递归调用所需保存的信息构成运行时栈的一个工作记录，在每进入下一层递归调用时，系统就建立一个新的,工作记录,，并把这个工作记录进栈成为运行时栈新的栈顶；每返回一层递归调用，就退栈一个工作记录。因为栈顶的工作记录必定是当前正在运行的递归函数的工作记录，所以栈顶的工作记录也称为,活动记录。,19,6.5递归算法的效率分析,斐波那契数列,Fib(n),的递推定义是：,求第,n,项斐波那契数列的,递归函数,如下：,long Fib(,int,n),if(n=0|n=1)return n;,/,递归出口,else return Fib(n-1)+Fib(n-2);,/,递归调用,20,用归纳法可以证明求,Fib(,n,),的递归,调用次数,等于,2,n,-1,；,计算斐波那契数列的递归函数,Fib(,n,),的,时间复杂度为,O,(2,n,),。,计算斐波那契数列,Fib(,n,),问题，我们也可根据公式写出,循环方式求解的函数如下：,图,6-6,Fib(5),的递归调用树,21,long Fib2(,int,n),long,int oneBack,twoBack,current;,int,i;,if(n=0|n=1)return n;,else,oneBack,=1;,twoBack,=0;,for(i=2;i=n;i+),current=,oneBack,+,twoBack,;,twoBack,=,oneBack,;,oneBack,=current;,return current;,22,上述循环方式的计算斐波那契数列的函数,Fib2(n),的时间复杂度为,O(n),。,对比循环结构的,Fib2(n),和递归结构的,Fib(n),可发现，,循环结构,的,Fib2(n),算法在计算第,n,项的斐波那契数列时,保存了,当前已经计算得到的,第,n,-1,项和第,n,-2,项的斐波那契数列,，因此其,时间复杂度为,O,(,n,),；,而,递归结构,的,Fib(n),算法在计算第,n,项的斐波那契数列时，,必须首先计算第,n-1,项和第,n-2,项的斐波那契数列,，而某次递归计算得出的斐波那契数列，如,Fib(n-1)、Fib(n-2),等,无法保存,，下一次要用到时还需要重新递归计算，因此其,时间复杂度为,O(2,n,),。,23,6.6递归算法到非递归算法的转换,有些问题需要用低级程序设计语言来实现，而低级程序设计语言（如汇编语言）一般不支持递归，此时需要采用问题的非递归结构算法。一般来说，存在如下,两种情况的递归算法,。,（1）存在,不借助堆栈的循环结构的非递归算法,，如阶乘计算问题、斐波那契数列的计算问题、折半查找问题等。这种情况，,可以直接选用循环结构的算法。,（2）存在,借助堆栈的循环结构的非递归算法,，所有递归算法都可以借助堆栈转换成循环结构的非递归算法，如下边例6-4设计的汉诺塔问题的借助堆栈的循环结构的非递归算法。此时,可以把递归算法转换成相应的非递归算法，,有两种转换方法：,一种方法是借助堆栈,，用非递归算法形式化模拟递归算法的执行过程；,另一种方法是,根据要求解问题的特点，,设计借助堆栈的循环结构算法。,这两种方法都需要使用堆栈，这是因为堆栈的后进先出特点正好和递归函数的运行特点相吻合。下面讨论的例,6-4,是第二种情况下的第一种转换方法的例子,24,顺序堆栈的,数据元素类型,Datatype,定义如下：,Struct DataType,int retAddr,;,/,代表返回地址的数值,int nPara,;,/,参数1,char,fromPegPara,;,/,参数2,char,toPegPara,;,/,参数3,char,auxPegPara,;,/,参数4,;,例6-4 借助堆栈模拟系统的运行时栈，把汉诺塔问题的递归算法转换为非递归算法。,25,算法设计：汉诺塔问题的,非递归函数设计如下：,void,SimTowers,(,int,n,char,fromPeg,char,toPeg,char,auxPeg,),/,把,n,个盘子从,fromPeg,柱借助,auxPeg,柱移到,toPeg,柱,DataType currArea,;,SeqStack,s;,char temp;,short,int,i;,26,/当前工作区初始化,currArea,.,retAddr,=1;,currArea,.,nParam,=n;,currArea,.,fromParam,=,fromPeg,;,currArea,.,auxParam,=,auxPeg,;,currArea,.,toParam,=,toPeg,;,S.Push(,CurrArea,);,27,/以下模拟递归出口,start:,if(,currArea,.,nPara,=1),cout,move disk 1 from peg,currArea,.,fromParam,to Peg,currArea,.,toParam,endl,;,i=,currArea,.,retAddr,;,currArea,=s.Pop();,switch(i),case1:,goto,lable1;,case2:,goto,lable2;,case3:,goto,lable3;,28,/以下模拟递归自调用过程,s.Push(,currArea,);,currArea,.,nParam,-;,Temp,=,currArea,.,auxParam,;,currArea,.,toParam,=,currArea,.,toParam,;,currArea,.,toParam,=temp;,currArea,.,retAddr,=2;,goto,start;,29,/以下模拟返回第一次递归调用,lable2:,cout,move disk“,currarea,.,nParam,from peg,currarea,.,fromPegParam,to peg“,currarea,.,toParam,endl,;,s.Push(,currArea,);,currArea,.,nParam,-;,temp =,currArea,.,auxParam,;,currArea,.,toParam,=,currArea,.,toParam,;,currArea,.,toParam,=temp;,currArea,.,retAddr,=3;,goto,start;,30,/以下模拟返回第二次递归调用,lable3:,i=,currarea,.,retAddr,;,currArea,=s.Pop();,switch(i),case 1:,goto,lable1;,case 2:,goto,lable2;,case 3:,goto,lable3;,/,以下模拟返回主调函数,lable1:,return;,由于汉诺塔问题本身算法的复杂度就是,O(2,n,),，,所以这个模拟算法的,时间复杂度也是,O(2,n,),。,31,6.7设计举例,6.7.1,一般递归算法设计举例,例6-5 设计一个输出如下形式数值的递归算法。,n n n .n,.,3 3 3,2 2,1,32,问题分析：,该问题可以看成由两部分组成：一部分是输出一行值为,n,的数值；另一部分是原问题的子问题，其参数为,n-1。,当参数减到0时不再输出任何数据值，因此递归的出口是当参数,n0,时空语句返回。,算法设计：递归算法设计如下：,void Display(,int,n),int,i;,for(i=1;i=n;i+),cout,setw,(s)n;,cout,0)Display(n-1);/,递归,/,n=0,为递归出口，递归出口为空语句,33,例6-6 设计求解,委员会问题,的算法。委员会问题是：从一个有,n,个人的团体中抽出,k(,k,n,),个人组成一个委员会，计算共有多少种构成方法。,问题分析：,从,n,个人中抽出,k,(,k,n,),个人的问题是一个组合问题。把,n,个人固定位置后，从,n,个人中抽出,k,个人的问题可分解为两部分之和：第一部分是第一个人包括在,k,个人中，第二部分是第一个人不包括在,k,个人中。对于第一部分，则问题简化为从,n,-1,个人中抽出,k,-1,个人的问题；对于第二部分，则问题简化为从,n,-1,个人中抽出,k,个人的问题。图6-7给出了,n,=5,k,=2,时问题的分解示意图。,34,图,6-7,委员会问题分解示意图,35,当,n,=,k,或,k,=0,时，该问题可直接求解，数值均为1，这是算法的递归出口。因此，委员会问题的,递推定义式,为：,int Comm,(,int,n,int,k),if(n n)return 0;,if(k=0)return 1;,if(n=k)return 1;,return,Comm,(n-1,k-1)+,Comm,n-1,k);,36,例6-7 求两个正整数,n,和,m,最大公约数的,递推定义式,为：,要求：,（1）编写求解该问题的递归算法；,（2）分析当调用语句为,Gcd,(30,4),时算法的执行过程和执行结果；,（3）分析当调用语句为,Gcd,(97,5),时算法的执行过程和执行结果；,（4）编写求解该问题的循环结构算法。,37,解：（1）递归算法如下：,int Gcd,(,int,n,int,m),if(n 0|m n)return,Gcd,(m,n);,else return,Gcd,(m,n%m);,（2）,调用语句为,Gcd,(30,4),时，因,mn，,递归调用,Gcd,(4,2)；,因,mn，,递归调用,Gcd,(97,5)；,因,mn，,递归调用,Gcd,(5,2)；,因,mn，,递归调用,Gcd,(2,1)；,因,mn，,递归调用,Gcd,(1,0)；,因,m=0，,到达递归出口，函数最终返回值为,n=1，,即5和97的最大公约数为1。,38,6.7.2 回溯法及其,设计举例,回溯法是递归算法的一种特殊形式，回溯法的,基本思想是：,对一个包括有很多结点，每个结点有若干个搜索分支的问题，把原问题分解为对若干个子问题求解的算法。,当搜索到某个结点、发现无法再继续搜索下去时，就让搜索过程回溯退到该结点的前一结点，继续搜索这个结点的其他尚未搜索过的分支,；如果发现这个结点也无法再继续搜索下去时，就让搜索过程回溯（即退回）到这个结点的前一结点继续这样的搜索过程；这样的搜索过程一直进行到搜索到问题的解或搜索完了全部可搜索分支没有解存在为止。,39,