经典递归问题--汉诺塔(java实现)
经典递归问题–汉诺塔(java实现)
一、什么是递归
1.递归的定义
程序调用自身的编程技巧称为递归；
如求阶乘：
public static int fac(int n) {
if(n == 1) {
return 1;
}else {
return fac(n-1) * n;
}
}
public static void main(String[] args) {
int ret = fac(5);
System.out.println(ret);
}这里就是在fac()函数内部 不断调用 fac函数 ；通过简单的代码来实现复杂过程。
2.递归过程的详细解释
我们通常能够看懂简单的递归代码，但是自己上手写的时候却总是想不到思路，这是因为我们对递归的理解不够深入；
下面是对递归的深入理解：
递归是一个整体的动作 递归中 递 和 归 分别是两个独立的过程 递 --> 开辟函数栈帧， 归 --> 销毁函数栈帧 程序执行递归的的过程 是先递后归的过程， 也是不断开辟函数栈帧把参数传递过去 ；同时不断返回数值，然后销毁函数栈帧的过程 （关于什么是函数栈帧可以看我的相关博客：http://t.csdnimg.cn/opIPf <关于return单一返回值> 的最后部分内容 ）
下面是图例解释:
我们在上述图片可以看到： 红色箭头所指部分均是 “递过程”
蓝色箭头所指向的部分 均是归过程
而函数栈帧内 就说我们常说的 方法体，也可以叫做递推公式
二、汉诺塔问题
在了解完递归的原理之后，我们来解决一下汉诺塔的问题
1.汉诺塔(hanoi)的介绍
有三根相邻的柱子，标号为A,B,C， A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子C上 每次只能移动一个圆盘，并且只能小圆片只能放在大圆盘上。
不了解汉诺塔的同学可以尝试一下在线汉诺塔小游戏：汉诺塔小游戏 (fuyeor.com)
总的来说：
如果只有一个圆盘，只需要移动一次 ： 即 A->C
如果有三个圆盘，则需要移动（23 - 1次）次，即 A->C B->C C->A A->C B->A B->C A->C
2.过程分析
从上述过程我们知道，随机盘数的增加，其移动次数成指数式增长，代码也会变得复杂；
为了缩减代码复杂度，我们使用 递归方法来解决问题:
我们先假设只有一个盘子:方法很简答，就是从A->C 这里A表示的是起始的柱子，C表示结束的柱子
我们通常不只是有一个盘子，但是最后一个盘子一定是从A->C，所以我们把 N个盘子分成两部分：
第一部分是上面N-1个盘子，要先把这部分当作一个整体移动到 B柱（这里B柱表示的是过度柱），再把最下面的柱子 从A->C
剩下的问题就是把 剩下N-1个柱子从 B 移动到C 了
到这里大家是不是感觉有点熟悉了；我们要把移动这 N-1个盘子 只需要把 上面的 （N-1）-1个盘子移动到==A柱（此时的中间柱）==
然后把最下面的盘子移动到 B->C 就可以了
我们会发现：移动N-1个盘子与移动N个盘子思路一致，只是起始位置变成了B，中间位置变成了A
那么我们是不是可以一直按着这个思路，移动N-i个盘子，直到最后 只剩一个盘子 即（n-1）== 1时，移动一次就结束了
那我们总结一下思路：
- 第一步：把上面N-1个盘子 移动到中间位置
- 第二步：把最底下的盘子 从起始位置移动到结束位置
- 第三步：把上面N-1个盘子从**中间位置（即hanoi(n-1)的起始位置）**移动到结束位置
3.代码分析：
按照上述过程，我们写出如下代码
public static void hanoi(int n,char pos1,char pos2, char pos3) { //这里参数n表示要移动的盘数，pos1表示起始位置，pos2表示中间位置，pos3表示结束位置
//如果只有一个盘子的情况下:
if(n == 1) {
move(pos1,pos2);
}else {
//第一步：把上面N-1个盘子 移动到中间位置
hanoi(n-1,pos1,pos3,pos2);
//第二步：把最底下的盘子 从起始位置移动到结束位置
move(pos1,pos2);
//第三步：把上面N-1个盘子从**中间位置（即hanoi(n-1)的起始位置）**移动到结束位置
hanoi(n-1,pos2,pos1,pos3)
}
}
public static void move(char pos1, char pos2) {
System.out.println(pos1+"->"+pos2);
}
public static void main(String[] args) {
hanoi(3,'A','B','C');
}这里参数n表示要移动的盘数，pos1表示起始位置，pos2表示中间位置，pos3表示结束位置
运行结果：
static void main(String[] args) {
hanoi(3,'A','B','C');
}这里参数n表示要移动的盘数，pos1表示起始位置，pos2表示中间位置，pos3表示结束位置
运行结果：
