《Java递归例子》由会员分享，可在线阅读，更多相关《Java递归例子（36页珍藏版）》请在金锄头文库上搜索。
1、wordJava中的经典递归/汉诺塔问题(递归)古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上如图。有一个和尚想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求打印移动的步骤。如果只有一个盘子，如此不需要利用B座，直接将盘子从A移动到C。 如果有2个盘子，可以先将盘子1上的盘子2移动到B；将盘子1移动到c；将盘子2移动到c。这说明了：可以借助B将2个盘子从A移动到C，当然，也可以借助C将2个盘子从A移动到B。 如果有3个盘子，那么根据2个盘子的结论，
2、可以借助c将盘子1上的两个盘子从A移动到B；将盘子1从A移动到C，A变成空座；借助A座，将B上的两个盘子移动到C。这说明：可以借助一个空座，将3个盘子从一个座移动到另一个。 如果有4个盘子，那么首先借助空座C，将盘子1上的三个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的三个盘子移动到C。package org;import java.util.Scanner;public class Tower public static void main(String args) System.out.println(输入盘子的个数：);Scanner sc=new Scanne
3、r(System.in);int n=sc.nextInt();tower(n,A,B,C);public static void tower(int n,char a, char b, char c)if(n!=0)tower(n-1,a,c,b);System.out.println(move disk +n+t+from+a+t+to +c);c=a;tower(n-1,b,a,c);/-/斐波那契级数(递归,当n比拟大时，效率比拟低)package org;import java.util.Scanner;public class Fib public static long fib(
4、int n)if(n=1 | n=2)return 1;elsereturn fib(n-1)+fib(n-2);/* 测试 */public static void main(String args) System.out.println(输入一个整数：);Scanner sc=new Scanner(System.in);int n=sc.nextInt();System.out.println(结果为：+fib(n);/-/最大公约数(递归)package org;import java.util.Scanner;public class MaxGcd /* 递归实现 */public
5、static int gcd(int m, int n)if(n=0)return m;else if(m=n)while(n!=0)int rem=m % n;m=n;n=rem;elsegcd2(n,m);return m;/* 测试 */public static void main(String args) System.out.println(请输入两个整数m和n);Scanner sc=new Scanner(System.in);int m=sc.nextInt();int n=sc.nextInt();System.out.println(m+和+n+的最大公约数为：+gcd(
6、m,n);/-/简单的0/1背包问题(递归)： 设一背包可容物品的最大质量为m，现有n件物品，质量为m1，m2，.，mn，mi均为正整数，要从n件物品中挑选假如干件，/使背包的质量之和正好为mpackage org;public class Bag01 public static boolean knap(int weight, int a, int n)if(n=an-1) /能放if(knap(weight-an-1,a,n-1)return true;elsereturn knap(weight,a,n-1);/不放else/不能放return knap(weight,a,n-1);/不
7、放/* 测试 */public static void main(String args) int weight=68;int a=16,21,6,31,2,5,7,8,10,15;boolean flag=knap(weight,a,10);System.out.println(flag);/-/求n!package org;import java.util.Scanner;public class Factorial /* 递归实现 */public static long fac(int n)if(n=0 | n=1)return 1;elsereturn (n * fac(n-1);/
8、* 非递归实现 */public static long fac2(int n)int sum=1;if(n=0 | n=1)return 1;for(int i=2;i=n;i+)sum*=i;return sum;/* 测试 */public static void main(String args) System.out.println(输入一个整数：);Scanner sc=new Scanner(System.in);int n=sc.nextInt();System.out.println(n+！=+fac(n);/-/求n个数的排列(递归)package org;/* permu
9、tation: 排列 */public class Permutation public static void perm(int data, int start, int end)if(start=end-1)for(int i=0;iend;i+)System.out.print(datai);System.out.println();elsefor(int i=start;irightMax ? leftMax : rightMax;public static int findMin(int srcData, int left, int right)if(left=right)return srcDataleft;int mid=(left+right)/2;int leftMin=findMin(srcData, left, mid);int rightMin=findMin(srcData,mid+1,right);return leftMinrightMin ? leftMin : rightMin;/* 测试 */public static void main(String arg
