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

第第5 5章章 递归递归 5.1n阶乘5.2斐波纳契数5.3将输入的词组以先进后出法打印5.4一个典型的递归范例：汉诺塔5.5程序集锦5.6思考题1第第5 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.1n5.1n阶乘阶乘publicintfact(intn)intans;if(n=1)ans=1;elseans=nfact(n-1);returnans;在编写递归程序时，千万要记住必须有一个结束点，可以使函数往上追溯直到结束。如上例中，当n=1时，1!=1即为其结束点。35.25.2斐波纳契数斐波纳契数 斐波纳契数（Fibonaccinumber）表示某一数为其前两个数的和，假设n0=1，n1=1，则n2=n1+n0=1+1=2n3=n2+n1=2+1=3所以ni=ni1+ni245.1n5.1n阶乘阶乘其递归程序如下：publicintfibon(intn)intans;if(n=0|n=1)ans=1;elseans=fibon(n-1)+fibon(n-2);return(ans);55.35.3将输入的词组以先进后出法打印将输入的词组以先进后出法打印 编译程序在处理递归时，会借助栈将调用本身函数的下一个语句的地址存储起来，待执行完后，再将栈的数据一一出栈处理。下面以一范例说明。此例是将输入的词组（word）以先进后出的方式打印出来，其程序如下：publicstaticvoidpush_f()/新增函数DataInputStreamin=newDataInputStream(System.in);65.35.3将输入的词组以先进后出法打印将输入的词组以先进后出法打印if(top=MAX-1)/当栈已满，则显示错误System.out.print(nStackisfull!n);elsetop+;System.out.print(nPleaseenteritemtoinsert:);System.out.flush();trystacktop=in.readLine();catch(IOExceptione)System.out.println();75.45.4一个典型的递归范例：汉诺塔一个典型的递归范例：汉诺塔 19世纪在欧洲有一游戏称为汉诺塔（TowersofHanoi），有64个大小不同的金盘子，3个镶钻石的柱子分别为A、B、C，现要求把64个金盘子从A柱子借助B柱子移到C柱子，游戏规则为：（1）每次只能移动一个盘子。（2）盘子有大小之分，大盘子必须在下，小盘子在上。假设有n个金盘子（1，2，3，n-1），数字越大表示重量越重，其搬移的算法如下：85.45.4一个典型的递归范例：汉诺塔一个典型的递归范例：汉诺塔假设n=1则搬移第1个盘子从A到C否则：搬移n-1个盘子从A到B，借助C搬移第n个盘子从A到C搬移n-1个盘子从B到C，借助A编写的程序如下：95.45.4一个典型的递归范例：汉诺塔一个典型的递归范例：汉诺塔publicstaticvoidHanoiTower(intn,charfrom,charaux,charto)if(n=1)System.out.print(Movedisk+n+from+from+-+to+n);else/将A上n-1个盘子借助C移到BHanoiTower(n-1,from,to,aux);System.out.print(Movedisk+n+from+from+-+to+n);/将B上n-1个盘子借助A移到CHanoiTower(n-1,aux,from,to);105.55.5程序集锦程序集锦 1利用递归的方式计算n阶乘2利用递归方式计算斐波纳契数3利用递归方式解汉诺塔问题115.65.6思考题思考题 1.请举几个使用递归的例子，并详细说明其递归的做法。2.继续上题，将所举的例子以C语言来执行。3.试计算出有n个金盘子在汉诺塔B柱子，共需移动多少次？12