使用递归实现汉诺塔

public class Main {public static void move(char pos1,char pos2) {System.out.print(pos1+" => "+pos2+" ");}public static void han(int n,char pos1,char pos2,char pos3) {if(n == 1) {move(pos1,pos3);return ;}han(n-1,pos1,pos3,pos2);move(pos1,pos3);han(n-1,pos2,pos1,pos3);}public static void main(String[] args) {han(1,'A','B','C');System.out.println();han(2,'A','B','C');System.out.println();han(3,'A','B','C');}
}

求移动的次数

package test04;public class Main {static int sum = 0;public static void move(char pos1,char pos2) {System.out.print(pos1+" => "+pos2+" ");sum++;}public static void han(int n,char pos1,char pos2,char pos3) {if(n == 1) {move(pos1,pos3);return ;}han(n-1,pos1,pos3,pos2);move(pos1,pos3);han(n-1,pos2,pos1,pos3);}public static void main(String[] args) {han(1,'A','B','C');System.out.println(sum);System.out.println();sum = 0;han(2,'A','B','C');System.out.println(sum);System.out.println();sum = 0;han(3,'A','B','C');System.out.println(sum);System.out.println();}
}

2的n次方减去1