数据结构java版第5章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,5,章 递归,5.1 n,阶乘,5.2,斐波纳契数,5.3,将输入的词组以先进后出法打印,5.4,一个典型的递归范例：汉诺塔,5.5,程序集锦,5.6,思考题,1,第,5,章 递归,一个调用它本身的函数称为递归函数。,5.1 n,阶乘,n!=n (n-1)!,(n-1)!=(n-1)(n-2)!,(n-2)!=(n-2)(n-3)!,1!=1,从上述公式可得知其相同的规则为：某一数,A,的阶乘为本身,A,乘以,(A-1),的阶乘。其程序如下：,2,5.1 n,阶乘,public,int,fact(int,n),int,ans,;,if(n,=1),ans,=1;,else,ans,=nfact(n-1);,return,ans,;,在编写递归程序时，千万要记住必须有一个结束点，可以使函数往上追溯直到结束。如上例中，当,n=1,时，,1!=1,即为其结束点。,3,5.2,斐波纳契数,斐波纳契数（,Fibonacci,number,）表示某一数为其前两个数的和，假设,n,0,=1,，,n,1,=1,，则,n,2,=n,1,+n,0,=1+1=2,n,3,=n,2,+n,1,=2+1=3,所以,n,i,=,n,i,1,+,n,i,2,4,5.1 n,阶乘,其递归程序如下：,public,int,fibon(int,n),int,ans,;,if(n,=0|n=1),ans,=1;,else,ans,=fibon(n-1)+fibon(n-2);,return(ans,);,5,5.3,将输入的词组以先进后出法打印,编译程序在处理递归时，会借助栈将调用本身函数的下一个语句的地址存储起来，待执行完后，再将栈的数据一一出栈处理。下面以一范例说明。此例是将输入的词组（,word,）以先进后出的方式打印出来，其程序如下：,public static void,push_f,()/,新增函数,DataInputStream,in=new,DataInputStream(System.in,);,6,5.3,将输入的词组以先进后出法打印,if(top,=MAX-1)/,当栈已满，则显示错误,System.out.print(n,Stack is full!n);,else,top+;,System.out.print(n,Please enter item to insert:);,System.out.flush,();,try,stacktop,=,in.readLine,();,catch(,IOException,e),System.out.println,();,7,5.4,一个典型的递归范例：汉诺塔,19,世纪在欧洲有一游戏称为汉诺塔（,Towers of Hanoi,），有,64,个大小不同的金盘子，,3,个镶钻石的柱子分别为,A,、,B,、,C,，现要求把,64,个金盘子从,A,柱子借助,B,柱子移到,C,柱子，游戏规则为：,（,1,）每次只能移动一个盘子。,（,2,）盘子有大小之分，大盘子必须在下，小盘子在上。,假设有,n,个金盘子（,1,，,2,，,3,，,，,n-1,），数字越大表示重量越重，其搬移的算法如下：,8,5.4,一个典型的递归范例：汉诺塔,假设,n=1,则搬移第,1,个盘子从,A,到,C,否则：,搬移,n-1,个盘子从,A,到,B,，借助,C,搬移第,n,个盘子从,A,到,C,搬移,n-1,个盘子从,B,到,C,，借助,A,编写的程序如下：,9,5.4,一个典型的递归范例：汉诺塔,public static void,HanoiTower(int,n,char,from,char,aux,char,to),if(n=1),System.out.print(Move,disk+n+from+from,+-+to+n);,else,/,将,A,上,n-1,个盘子借助,C,移到,B,HanoiTower(n-1,from,to,aux,);,System.out.print(Move,disk+n+from+from,+-+to+n);/,将,B,上,n-1,个盘子借助,A,移到,C,HanoiTower(n-1,aux,from,to);,10,5.5,程序集锦,1,利用递归的方式计算,n,阶乘,2,利用递归方式计算斐波纳契数,3,利用递归方式解汉诺塔问题,11,5.6,思考题,1.,请举几个使用递归的例子，并详细说明其递归的做法。,2.,继续上题，将所举的例子以,C,语言来执行。,3.,试计算出有,n,个金盘子在汉诺塔,B,柱子，共需移动多少次？,12,