递归算法经典案例

案例一：publicclassFibonacci{//一列数的规则如下:1、1、2、3、5、8、13、21、34，求第30位数是多少？使用递归实现publicstaticvoidmain(String[]args){System.out.println(Fribonacci(9));}publicstaticintFribonacci(intn){if(n=2)return1;elsereturnFribonacci(n-1)+Fribonacci(n-2);}}案例二：publicclassHanio1{/**汉诺塔（又称河内塔）问题其实是印度的一个古老的传说。开天辟地的神勃拉玛（和中国的盘古差不多的神吧）在一个庙里留下了三根金刚石的棒，*第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，*规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。计算结果非常恐怖(移动圆片的次数)18446744073709551615，*众僧们即便是耗尽毕生精力也不可能完成金片的移动了。*要求：输入一个正整数n，表示有n个盘片在第一根柱子上。输出操作序列，格式为“移动t从x到y”。每个操作一行，*表示把x柱子上的编号为t的盘片挪到柱子y上。柱子编号为A，B，C，你要用最少的操作把所有的盘子从A柱子上转移到C柱子上。*/publicstaticvoidmain(String[]args){inti=3;chara='A',b='B',c='C';hanio(i,a,b,c);}publicstaticvoidhanio(intn,chara,charb,charc){if(n==1)System.out.println(移动+n+号盘子从+a+到+c);else{hanio(n-1,a,c,b);//把上面n-1个盘子从a借助b搬到cSystem.out.println(移动+n+号盘子从+a+到+c);//紧接着直接把n搬动chanio(n-1,b,a,c);//再把b上的n-1个盘子借助a搬到c}}}案例三：publicclassRabbit{/*古典问题：3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？分析：首先我们要明白题目的意思指的是每个月的兔子总对数；假设将兔子分为小中大三种，兔子从出生后三个月后每个月就会生出一对兔子，那么我们假定第一个月的兔子为小兔子，第二个月为中兔子，第三个月之后就为大兔子，那么第一个月分别有1、0、0，第二个月分别为0、1、0，第三个月分别为1、0、1，第四个月分别为,1、1、1，第五个月分别为2、1、2，第六个月分别为3、2、3，第七个月分别为5、3、5……兔子总数分别为：1、1、2、3、5、8、13……于是得出了一个规律，从第三个月起，后面的兔子总数都等于前面两个月的兔子总数之和，即为斐波那契数列。*/publicstaticvoidmain(String[]args){inti=1;for(i=1;i=20;i++){System.out.println(兔子第+i+个月的总数为:+f(i));}}publicstaticintf(intx){if(x==1||x==2){return1;}else{returnf(x-1)+f(x-2);}}}