递归

递归

我们来说说递归，Hanoi塔就是一个经典的例子。刚刚上大一的时候当时并没有理解其中的原理。

设有三个柱子，A,B,C,A柱上有大小不同的64个盘子，大盘放在小盘的下面。下面我们想借助C柱将A柱移到B柱，每次只能移动一个盘子，大盘在下，小盘在上。那么你会怎么解决这个问题呢？

当有n个盘子，我们可以考虑为（n-1）个盘子，当（n-1）个盘子我们放好了，我们将（n-1）个盘子顺序移到C盘，再将第n个盘子移到B柱，是不是就解决了？

当（n-1）个盘子我们可以考虑为（n-2）个盘子，这样递归这，直到有3个盘子的数量是不是就很好解决了？

package reaiy;

public class Reaily {

public static void hanoi(int n,char a,char b,char c){

if(n>0){

hanoi(n-1,a,c,b);

System.out.println("移动第"+n+"个盘子，从"+a+"到"+b);

hanoi(n-1,c,b,a)

;

}

}

public static void main(String[] args){

hanoi(3,'a','b','c');

}

}

运行结果：

移动第1个盘子，从a到b

移动第2个盘子，从a到c

移动第1个盘子，从b到c

移动第3个盘子，从a到b

移动第1个盘子，从c到a

移动第2个盘子，从c到b

移动第1个盘子，从a到b