递归相关汉诺塔hanoi
递归的种种问题，也许理解的同学可能可以用一句话解释清楚，不理解的同学再怎么说也没办法理解！
递归的基本概念:
程序调用自身的编程技巧称为递归,
是函数自己调用自己.一个函数在其定义中直接或间接调用自身的一种方法,
它通常把一个大型的复杂的问题转化为一个与原问题相似的规模较小的问题来解决,
可以极大的减少代码量.递归的能力在于用有限的语句来定义对象的无限集合。
其实就是调用自己！
网上一个形象的比喻是这么说的：
你打开面前这扇门，看到屋里面还有一扇门。
你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它。
若干次之后，你打开面前的门后，发现只有一间屋子，没有门了。
然后，你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙打开了几扇门。
递归的三要素：
1、明确递归终止条件；（没有门了）
2、给出递归终止时的处理办法；（每次进去一个门的时候干点什么，或者什么也不干，就往回走）
3、提取重复的逻辑，缩小问题规模。（用钥匙 打开门进去）
例子 递归实现：1+2+3...+n = ？
public static void main(String[] args) {
System.out.println(addition(4));
}
/**
* 1+2+3...+n = ?
* 如果从1顺序相加一直加到n，求到n时候的总和是多少
* @param i
* @return
*/
public static int addition(int i) {
if (i > 0) {
return addition(i - 1) + i;//（用钥匙 打开门进去）
} else {//小于1的时候 （终止条件）
return 0; //返回零（递归终止时的处理办法）
}
}
下面是程序的流程图
汉诺塔实现
汉诺塔典故：
在世界中心贝拿勒斯（在印度北部）的圣庙里，
一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，
在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。
不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。
僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，
世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽
解决问题的关键,忽略小细节,注重大步骤:
A柱子把”共n-1”个盘借助C盘移动到B盘,完成一个大过程
A柱子把剩下的”第n”个盘直接移动到C盘,完成一个大过程
B柱子上的”共n-1”个盘借助A移动到C盘,又完成一个大过程
public static void main(String[] args) {
String A="A";
String B="B";
String C="C";
int i = 3;
hanoi(i,A,B,C);
System.out.println(numCount);
}
/**
* Hanoi
*/
public static void hanoi(int i,String A,String B,String C) {
numCount++;
if (i == 1) {
System.out.println("从"+A+"拿出 "+i+" 移动到"+C);
}else{
hanoi(i-1,A,C,B);
System.out.println("从"+A+"拿出 "+i+" 移动到"+C);
hanoi(i-1,B,A,C);
}
}
A借C把("共"n-1个)移动到B
原柱子->辅助柱子
C变成辅助,所以排在第二位,B变成目标;
hanoi(i-1,A,C,B);
B借A把("共"n-1)个移动到C
多个:辅助柱->目标柱子
A是辅助,所以排在第二位置,C变目标;
hanoi(i-1,B,A,C);
下面是汉诺塔 递归的流程图：