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

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