8第五章递归算法

,第二级,第三级,第四级,第五级,第,5,章 递归算法,5.1,递归的概念,5.2,递归算法的执行过程,5.3,递归算法的设计方法,5.4,设计举例,5.1,递归的概念,存在算法调用自己的情况：,若一个算法直接的或间接的,调用自己本身,，则称这个算法是递归算法。,阶乘,函数的,常见定义,是：,1,问题定义是递推的,也可,定义为：,写成,函数形式，则为：,这种函数定义的方法是,用阶乘函数自己本身定义了阶乘函数,，称公式（,6 3,）是阶乘函数的,递推定义式,。,2.,问题的解法存在自调用,例如：折半查找算法,查找,17,5.2,递归算法的执行过程,例,1,：阶乘的递归算法,public static long,fact(int,n),long,y;,if(n 0),throw new Exception(,参数错！,);,if(n=0)return 1;,else,y=fact(n-1);,return n*y;,设计一个计算,3,！,的主函数如下,用来说明递归算法的执行过程：,static void Main(string args),long,fn;,try,fn=fact(3);,Console.WriteLine(fn=+fn);,catch(Exception e),Console.WriteLine(e.Message);,主函数用,实参,n=3,调用了递归算法,fact(3),，,而,fact(3),要通过,调用,fact(2),、,fact(2),要通过,调用,fact(1),、,fact(1),要通过,调用,fact(0),来得出计算结果。,fact(3),的递归调用过程如下图所示，其中，,实线箭头表示函数调用，虚线箭头表示函数返回,，此函数在返回时函数名将带回返回值,。,main,.,.,.,fn,=,fact(3),return(3*y),1,1,2,6,fact(3),.,.,.,y,=,fact(2),return(2*y),.,.,.,fact(2),y,=,fact(1),.,.,.,y,=,fact(0),fact(1),fact(0),return 1,return(1*y),5.3,递归算法的设计方法,递归算法既是一种有效的,算法设计,方法，也是一种有效的,分析问题,的方法。,递归算法求解问题的,基本思想,是：对于一个较为复杂的问题，把原问题分解成若干个相对简单且类同的子问题，这样较为复杂的原问题就变成了相对简单的子问题；而简单到一定程度的子问题可以直接求解；这样，原问题就可递推得到解。,适宜于用递归算法求解的问题的,充分必要条件,是：,（,1,）问题具有某种可借用的类同自身的子问题描述的性质,（,2,）某一有限步的子问题（也称作本原问题）有直接的解存在。,当一个问题存在上述两个基本要素时，设计该问题的递归算法的方法是：,（,1,）把对原问题的求解表示成对子问题求解的形式。,（,2,）设计递归出口。,例,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,个盘子汉诺塔问题的递归求解示意图如图所示。,2,1,3,4,A,B,C,2,1,3,4,A,B,C,(a),4,A,B,C,2,1,3,(b),A,B,C,2,1,3,4,(d),A,B,C,2,1,3,4,(c),算法设计：,首先，盘子的个数,n,是必须的一个输入参数，对,n,个盘子,我们可从上至下依次编号为,1,2,n,；,其次，输入参数还需有,3,个柱子的代号,我们令,3,个柱子的参数名分别为,fromPeg,，,auxPeg,和,toPeg,；,最后由于此算法是模拟汉诺塔问题的求解过程，因此算法的输出是,n,个盘子从柱子,fromPeg,借助柱子,auxPeg,移动到柱子,toPeg,的移动步骤，我们设计每一步的移动为屏幕显示如下形式的信息：,Move Disk i from Peg X to Peg Y,public static void towers(int n,char fromPeg,char toPeg,char auxPeg),/,把,n,个圆盘从,fromPeg,借助,auxPeg,移至,toPeg,if(n=1),Console.WriteLine(move disk 1 from peg +fromPeg+to peg +toPeg);,return;,towers(n-1,fromPeg,auxPeg,toPeg);,Console.WriteLine(move disk +n+from peg +fromPeg+to peg +toPeg);,towers(n-1,auxPeg,toPeg,fromPeg);,static void Main(string args),towers(4,A,C,B);,递归算法把移动,n,个盘子的汉诺塔问题分解为移动,n-1,个盘子的汉诺塔问题，把移动,n-1,个盘子的汉诺塔问题分解为移动,n-2,个盘子的汉诺塔问题，,，把移动,2,个盘子的汉诺塔问题分解为移动,1,个盘子的汉诺塔问题。对于,1,个盘子的汉诺塔问题直接求解。在,1,个盘子的汉诺塔问题解决后，可以解决,2,个盘子的汉诺塔问题，,在,n-1,个盘子的汉诺塔问题解决后，可以解决,n,个盘子的汉诺塔问题。这样,n,个盘子的汉诺塔问题最终就得以解决。,递归算法的执行过程可,总结如下：,递归算法的执行过程是不断地自调用，直到到达递归出口才结束自调用过程；到达递归出口后，递归算法开始按最后调用的过程最先返回的次序返回；返回到最外层的调用语句时递归算法执行过程结束。,例,1,设计求解,委员会问题,的算法。委员会问题是：从一个有,n,个人的团体中抽出,k(kn),个人组成一个委员会，计算共有多少种构成方法。,问题分析,：从,n,个人中抽出,k(kn),个人的问题是一个组合问题。把,n,个人固定位置后，从,n,个人中抽出,k,个人的问题可分解为两部分之和：,第一部分,是第一个人包括在,k,个人中，,第二部分,是第一个人不包括在,k,个人中。对于第一部分，则问题简化为从,n-1,个人中抽出,k-1,个人的问题；对于第二部分，则问题简化为从,n-1,个人中抽出,k,个人的问题。,5.4,设计举例,下图给出了,n=5,k=2,时问题的分解示意图。,当,n=k,或,k=0,时，该问题可直接求解，数值均为,1,，这是算法的递归出口。因此，委员会问题的,递推定义式,为：,public static,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);,例,2,求两个正整数,n,和,m,最大公约数的递推定义式为：,要求：,（,1,）编写求解该问题的递归算法；,（,2,）分析当调用语句为,Gcd(30,4),时算法的执行过程和执行结果；,（,3,）分析当调用语句为,Gcd(5,97),时算法的执行过程和执行结果；,（,4,）编写求解该问题的循环结构算法。,(1),递归函数设计如下：,public static 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,。,（,4,）循环结构函数,public static int gcd2(int n,int m),int tn,tm,temp;,if(n 0|m n),tn=m;,tm=n;,else,tn=n;,tm=m;,while(tm!=0),temp=tn;,tn=tm;,tm=temp%tm;,return tn;,