蔡明志数据结构java 版第 5章.ppt

《蔡明志数据结构java 版第 5章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第5章递归5.1n阶乘5.2斐波纳契数5.3将输入的词组以先进后出法打印5.4一个典型的递归范例：汉诺塔5.5程序集锦5.6思考题1第5章递归一个调用它本身的函数称为递归函数。5.1n阶乘n!=n×(n-1)!…(n-1)!=(n-1)×(n-2)!(n-2)!=(n-2)×(n-3)!1!=1从上述公式可得知其相同的规则为：某一数A的阶乘为本身A乘以(A-1)的阶乘。其程序如下：25.1n阶乘publicintfact(intn){intans;if(n==1)ans=1;elseans=n×fact(n-1);re

2、turnans;}在编写递归程序时，千万要记住必须有一个结束点，可以使函数往上追溯直到结束。如上例中，当n=1时，1!=1即为其结束点。35.2斐波纳契数斐波纳契数（Fibonaccinumber）表示某一数为其前两个数的和，假设n0=1，n1=1，则n2=n1+n0=1+1=2n3=n2+n1=2+1=3…所以ni=ni–1+ni–245.1n阶乘其递归程序如下：publicintfibon(intn){intans;if(n==0

3、

4、n==1)ans=1;elseans=fibon(n-1)+fibon(n-2);

5、return(ans);}55.3将输入的词组以先进后出法打印编译程序在处理递归时，会借助栈将调用本身函数的下一个语句的地址存储起来，待执行完后，再将栈的数据一一出栈处理。下面以一范例说明。此例是将输入的词组（word）以先进后出的方式打印出来，其程序如下：publicstaticvoidpush_f(){//新增函数DataInputStreamin=newDataInputStream(System.in);65.3将输入的词组以先进后出法打印if(top>=MAX-1)//当栈已满，则显示错误System.out

6、.print("Stackisfull!");else{top++;System.out.print("Pleaseenteritemtoinsert:");System.out.flush();try{stack[top]=in.readLine();}catch(IOExceptione){}}System.out.println("");}75.4一个典型的递归范例：汉诺塔19世纪在欧洲有一游戏称为汉诺塔（TowersofHanoi），有64个大小不同的金盘子，3个镶钻石的柱子分别为A、B、C，现要求

7、把64个金盘子从A柱子借助B柱子移到C柱子，游戏规则为：（1）每次只能移动一个盘子。（2）盘子有大小之分，大盘子必须在下，小盘子在上。假设有n个金盘子（1，2，3，…，n-1），数字越大表示重量越重，其搬移的算法如下：85.4一个典型的递归范例：汉诺塔假设n=1则搬移第1个盘子从A到C否则：①搬移n-1个盘子从A到B，借助C②搬移第n个盘子从A到C③搬移n-1个盘子从B到C，借助A编写的程序如下：95.4一个典型的递归范例：汉诺塔publicstaticvoidHanoiTower(intn,charfrom,char

8、aux,charto){if(n==1)System.out.print("Movedisk"+n+"from"+from+"->"+to+"");else{//将A上n-1个盘子借助C移到BHanoiTower(n-1,from,to,aux);System.out.print("Movedisk"+n+"from"+from+"->"+to+"");////将B上n-1个盘子借助A移到CHanoiTower(n-1,aux,from,to);}}105.5程序集锦1．利用递归的方式计算n阶乘2．利用递归方式

9、计算斐波纳契数3．利用递归方式解汉诺塔问题115.6思考题1.请举几个使用递归的例子，并详细说明其递归的做法。2.继续上题，将所举的例子以C语言来执行。3.试计算出有n个金盘子在汉诺塔B柱子，共需移动多少次？12