第6章递归算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,6,章 递归算法,6.1,递归的概念,6.2,递归算法的执行过程,6.3,递归算法的设计方法,6.4,递归过程和运行时栈,6.5,递归算法的效率分析,6.6,递归算法到非递归算法的转换,6.7,设计举例,1,在下面二种情况中存在算法调用自己的情况：,若一个算法直接的或间接的,调用自己本身,，则称这个算法是递归算法。,（,1,）问题的定义是递推的,阶乘,函数的,常见定义,是：,6.1,递归的概念,2,也可,定义为：,写成,函数形式，则为：,这种函数定义的方法是,用阶乘函数自己本身定义了阶乘函数,，称上式为阶乘函数的,递推定义式,。,3,（,2,）问题的解法存在自调用,一个典型的例子是在,有序数组中,查找一个数据元素是否存在的,折半查找算法,。,如下例中查找元素,17,。,第一次,:,下标,0,1,2,3,4,5,6,7,元素值,1,3,4,5,17,18,31,33,low,mid,high,x,a(mid,),第二次,:,下标,0,1,2,3,4,5,6,7,元素值,1,3,4,5,17,18,31,33,low,mid,high,x,a(mid,),第三次,:,下标,0,1,2,3,4,5,6,7,元素值,1,3,4,5,17,18,31,33,low,high,x=a(mid),mid,BSrch=4,mid=(low+high),2,，注意是,整除,“,”,4,6.2,递归算法的执行过程,例,6-1,给出按照,阶乘函数的递推定义式,计算阶乘函数的递归算法，并给出,n=3,时递归算法的执行过程。,设计：按照,阶乘函数的递推定义式,计算阶乘函数的递归算法如下：,Function,Fact(n,%)As Double,If n high Then,BSearch,=-1,查找不成功,Else,mid=(low+high),2,If x=,a(mid,)Then,BSearch,=mid,查找成功,ElseIf,x,a(mid,)Then,BSearch,=,BSearch(a,xlow,mid-1),在小数区查找,Else,BSearch,=,BSearch(a,x,mid+1,high),在大数区查找,End If,End If,End Function,9,测试代码设计如下：,Private Sub Command1_Click(),Dim a(8)As Integer,a(0)=1:a(1)=3:a(2)=4:a(3)=5,a(4)=17:a(5)=18:a(6)=31:a(7)=33,Dim y%,Dim,bn,Print,数组,a,为：,For i=0 To 7,Print,a(i,);,Next,y=,InputBox,(,请输入你要找的元素！,),Print,bn,=,BSearch(a,y,0,7),If,bn,=-1 Then,Print,你要找的元素,&y&,不在数组,a,中！,Else,Print,你要找的元素,&y&,在数组,a,中的下标为,&,bn,&.,End If,End Sub,10,BSearch(a,x,0,7),的递归调用过程如下图所示，其中，,实箭头,表示过程,调用，虚箭头,表示过程的,返回值,。,BSearch(a,y,0,7),mid=3,BSearch,=,BSearch(a,y,4,7),Sub Command1_Click(),x=17,bn,=,BSearch(a,y,0,7),End Sub,BSearch(a,y,4,7),mid=5,BSearch,=,BSearch(a,y,4,4),BSearch(a,y,4,4),mid=4,BSearch,=4,4,4,4,11,6.3,递归算法的设计方法,递归算法既是一种有效的,算法设计,方法，也是一种有效的,分析问题,的方法。递归算法求解问题的,基本思想,是：对于一个较为复杂的问题，把原问题分解成若干个相对简单且类同的子问题，这样较为复杂的原问题就变成了相对简单的子问题；而简单到一定程度的子问题可以直接求解；这样，原问题就可递推得到解。,并不是每个问题都适宜于用递归算法求解。适宜于用递归算法求解的问题的,充分必要条件,是：,（,1,）问题具有某种可借用的类同自身的子问题描述的性质；,（,2,）某一有限步的子问题（也称作本原问题）有直接的解存在。,当一个问题存在上述两个基本要素时，设计该问题的,递归算法的方法,是：,（,1,）把对原问题的求解设计成包含有对子问题求解的形式。,（,2,）设计递归出口。,12,例,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,个盘子汉诺塔问题的递归求解示意图如下图所示。,13,n,-1,n,原柱,A,辅助柱,B,目标柱,C,14,算法设计：首先，盘子的个数,n,是必须的一个输入参数，对,n,个盘子,我们可从上至下依次编号为,1,2,n,；,其次，输入参数还需有,3,个柱子的代号,我们令,3,个柱子的参数名分别为,fromPeg,，,auxPeg,和,toPeg,；,最后，汉诺塔问题的求解是一个处理过程，因此算法的输出是,n,个盘子从柱子,fromPeg,借助柱子,auxPeg,移动到柱子,toPeg,的移动步骤，我们设计每一步的移动为屏幕显示如下形式的信息：,Move Disk i from Peg X to Peg Y,这样，汉诺塔问题的,递归算法可设计如下,：,15,Sub,towers(n,%,fromPeg,$,toPeg,$,auxPeg,$),If n=1 Then,递归出口,Print move disk1 from peg&,fromPegto peg&,toPeg,Else,Call,towers(n,-1,fromPeg,auxPeg,toPeg,),把,n-1,个圆盘从,fromPeg,借助,toPeg,移到,auxPeg,Print move disk&n&from peg&,fromPeg,&to peg&,toPeg,把圆盘,n,从,fromPeg,直接移到,toPeg,Call,towers(n,-1,auxPeg,toPeg,fromPeg,),把,n-1,个圆盘从,auxPeg,借助,fromPeg,移到,toPeg,End If,End Sub,16,测试代码如下,：,Private Sub Command1_Click(),Call towers(4,A,C,B),End Sub,程序运行的输出信息如下：,17,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,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,18,从程序的运行输出信息可见，上述算法实现了递归求解汉诺塔问题。递归算法把移动,n,个盘子的汉诺塔问题分解为移动,n-1,个盘子的汉诺塔问题，把移动,n-1,个盘子的汉诺塔问题分解为移动,n-2,个盘子的汉诺塔问题，,，把移动,2,个盘子的汉诺塔问题分解为移动,1,个盘子的汉诺塔问题。对于,1,个盘子的汉诺塔问题直接求解。在,1,个盘子的汉诺塔问题解决后，可以解决,2,个盘子的汉诺塔问题，,在,n-1,个盘子的汉诺塔问题解决后，可以解决,n,个盘子的汉诺塔问题。这样,n,个盘子的汉诺塔问题最终就得以解决。,结合本节和,6.2,节的讨论，我们可总结如下：递归算法的执行过程是不断地自调用，直到到达递归出口才结束自调用过程；到达递归出口后，递归算法开始按最后调用的过程最先返回的次序返回；返回到最外层的调用语句时递归算法执行过程结束。,19,6.4,递归过程和运行时栈,对于非递归函数，调用函数在调用被调用函数前，系统要,保存,以下两类,信息,：,（,1,）调用函数的返回地址（从而能执行下一语句）；,（,2,）调用函数的局部变量值。,当执行完被调用函数，返回调用函数前，系统首先要,恢复,调用函数的,局部变量值,，然后,返回,调用函数的,返回地址,。,递归函数被调用时，系统要做的工作和非递归函数被调用时系统要作的工作在,形式上,类同，但保存信息的,内容,和,方法,不同。,20,保存内容：,每一层递归调用所需要保存的信息构成一个,工作记录,，通常包括如下内容：,（,1,）本次递归调用中的局部变量值；,（,2,）返回地址即本次递归过程调用语句的后继语句的地址；,（,3,）本次调用中与形参结合的实参值，包括函数名、引用参数与数值参数等。,工作记录,局部变量 返回地址 参 数,21,保存方法,:,递归函数被调用时，系统在运行递归函数前也要保存上述两类信息。但因为递归的函数的运行特点，是最后被调用的函数要最先被返回，若按非递归函数那样保存信息，显然要出错。,由于堆栈的后进先出特性正好与递归函数调用和返回的过程吻合，因此，高级程序设计语言利用堆栈保存递归函数调用的信息，系统用于保存递归函数调用信息的堆栈称为,运行时栈,。,运行时栈示意图,栈顶,栈底,局部变量,m,返回地址,m,参 数,m,局部变量,2,返回地址,2参 数,2,局部变量,1,返回地址,1,参 数,1,22,递归函数被调用时，,在每进入下一层递归调用时，系统就建立一个新的工作记录，并把这个工作记录进栈成为运行时栈新的栈顶；每返回一层递归调用，就退栈一个工作记录。,因为栈顶的工作记录必定是当前正在运行的递归函数的工作记录，所以,栈顶的工作记录,也称为,活动记录,。,工作记录,活动记录,运行时栈示意图,栈顶,栈底,局部变量,m,返回地址,m,参 数,m,局部变量,2,返回地址,2,参 数,2,局部变量,1,返回地址,1,参 数,1,23,我们以计算阶乘的递归函数为例，说明递归函数调用时运行时栈中工作记录的变化过程。为了更好地说明局部变量值的情况，我们把程序做了一些修改,(,以下红色部分,),。,Function,Fact(n,%)As Double,If n 0 Then,MsgBox,参数错了！,Fact=-1,ElseIf,n=0 Then,Fact=1,Else,Fact=n*,Fact(n,-1),End If,End Function,左边为以前的代码,Function,Fact(n,%)As Double,Dim x%,y As Double,If n 0 Then,MsgBox,参数错了！,Fact=-1,ElseIf,n=0 Then,Fact=1,Else,x=n-1,y=,Fact(x,),Fact=n*y,End If,End Function,24,由于函数的地址是系统动态分配的，调用函数的返回地址因此也是动态变化的，不好给出具体数值，故下图中没有给出调用函数的返回地址。,栈顶,3,2,1,栈底,0,n,x,y,Fact,初始时,运行时栈的变化过程,栈顶,3,2,1,栈底,0,3,*,*,*,n,x,y,Fact,调用,Fact(3),栈顶,3,2,1,2,*,*,*,栈底,0,3,2,*,*,n,x,y,Fact,调用,Fact(2),栈顶,3,2,1,*,*,*,1,2,1,*,*,栈底,0,3,2,*,*,n,x,y,Fact,调用,Fact(1),栈顶,3,0,*,*,1,2,1,0,12,1,*,*,栈底,0,3,2,*,*,n,x,y,Fact,调用,Fact(0),栈顶,3,2,1,0,1,1,1,2,1,*,*,栈底,0,3,2,*,*,n,x,y,Fact,返回,Fact(0),栈顶,3,2,1,2,1,1,2,栈底,0,3,2,*,*,n,x,y,Fact,返回,Fact(1),栈顶,3,2,1,栈底,0,3,2,2,6,n,x,y,Fact,返回,Fact(2),栈顶,3,2,1,栈底,0,n,x,y,Fact,返回,Fact(3),Function,Fact(n,%)As Double,Dim x%,y As Double,If n 0 Then Display n-1,End Sub,Private Sub Command1_Click(),Dim x%,x=,Val(InputBox,(,请输入,n,：,),Display x,End Sub,43,例,6-6,设计求解,委员会问题,的算法。委员会问题是：从一个有,n,个人的团体中抽出,k(kn),个人组成一个委员会，计算共有多少种构成方法。,问题分析,：从,n,个人中抽出,k(kn),个人的问题是一个组合问题。即求组合数公式,C(n,k,),。由于要所用递归算法,大家容易想到公式,:,C(n,k,)=C(n-1,k-1)+C(n-1,k),这个公式大家可以这样理解,:,把,n,个人固定位置后从,n,个人中抽出,k,个人的问题可分解为两部分之和：第一部分是第一个人包括在,k,个人中，第二部分是第一个人不包括在,k,个人中。对于第一部分，则问题简化为从,n-1,个人中抽出,k-1,个人的问题；对于第二部分，则问题简化为从,n-1,个人中抽出,k,个人的问题。,44,当,n=k,或,k=0,时，该问题可直接求解，数值均为,1,，这是算法的递归出口。因此，委员会问题的,递推定义式,为：,Function,Comm(n,%,k%)As Double,If n n Then,Comm,=0,ElseIf,k=0 Then,Comm,=1,ElseIf,n=k Then,Comm,=1,Else,Comm,=,Comm(n,-1,k-1)+,Comm(n,-1,k),End If,End Function,Private Sub Command1_Click(),Dim x%,y%,x=,Val(InputBox,(,请输入,n,的值：,),y=,Val(InputBox,(,请输入,k,的值：,),Print,Comm(x,y),End Sub,45,例,6-7,求两个正整数,n,和,m,最大公约数的递推定义式为：,要求：,（,1,）编写求解该问题的递归算法；,（,2,）分析当调用语句为,Gcd(30,4),时算法的执行过程和执行结果；,（,3,）分析当调用语句为,Gcd(5,97),时算法的执行过程和执行结果；,（,4,）编写求解该问题的循环结构算法。,46,解：（,1,）,递归算法如下：,Function,Gcd(n,%,m%),If n 0 Or m n Then,Gcd,=,Gcd(m,n),Else,Gcd,=,Gcd(m,n Mod m),End If,End Function,Private Sub Command1_Click(),Dim x%,y%,x=,Val(InputBox,(,请输入,n,的值：,),y=,Val(InputBox,(,请输入,m,的值：,),Print,Gcd(x,y),End Sub,47,（,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,。,48,（,4,）,循环结构算法,Function Gcd2(n%,m%)As Integer,Dim,tn,%,tm%,temp%,If n 0 Or m n Then,tn,=m,tm=n,Else,tn,=n,tm=m,End If,Do While tm 0,temp=,tn,tn,=tm,tm=temp Mod tm,Loop,Gcd2=,tn,End Function,49,