[面试题]递归算法实现的两个面试题

1，面试题：利用递归实现5*4*3*2*1的值：

public class FactorialDemo {

	public static void main(String[] args) {
		
		System.out.println("5*4*3*2*1="+factorial(5));
		
	}
	public static long factorial(long n){//求n!
		   if(n==0){
			   return 1;
		   }else{
			   return n*factorial(n-1);//利用递归n!=n*(n-1)!直到0
		   }
	}

}

    输出结果：5*4*3*2*1=120

 

 

2，面试题：利用递归实现三个盘子的汉落塔的过程：

public class FactorialDemo2 {

	static int count=1;
	public static void main(String[] args) {
		  char a='A',b='B',c='C';
		  int num=3;//圆盘的个数
		  hanoi(a,b,c,num);
	}
	
	public static void move(char j,char k){
	  System.out.println("第"+(factorialDemo2.count++)+
			  "步：将一个盘子从柱子"+j+"拿到柱子"+k);
	  }
	 
	public static void hanoi(char a,char b,char c,int n){  
	//假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,f(4)=15,
	//且f(k+1)=2*f(k)+1 那么汉落塔的算法：f(n)=2^n-1   n=圆盘的个数
	  if(n==1){
		  move(a,c);
	  }else{
		  hanoi(a,c,b,n-1);
		  move(a,c);
		  hanoi(b,a,c,n-1);
	  }
	 }

}

    输出结果：第1步：将一个盘子从柱子A拿到柱子B
                   第2步：将一个盘子从柱子A拿到柱子C
                   第3步：将一个盘子从柱子B拿到柱子C
                   第4步：将一个盘子从柱子A拿到柱子B
                   第5步：将一个盘子从柱子C拿到柱子A
                   第6步：将一个盘子从柱子C拿到柱子B
                   第7步：将一个盘子从柱子A拿到柱子B
                   第8步：将一个盘子从柱子A拿到柱子C
                   第9步：将一个盘子从柱子B拿到柱子C
                   第10步：将一个盘子从柱子B拿到柱子A
                   第11步：将一个盘子从柱子C拿到柱子A
                   第12步：将一个盘子从柱子B拿到柱子C
                   第13步：将一个盘子从柱子A拿到柱子B
                   第14步：将一个盘子从柱子A拿到柱子C
                   第15步：将一个盘子从柱子B拿到柱子C

 

  

    汉落塔相关资料：http://baike.baidu.com/view/191666.htm