经典递归问题--汉诺塔(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表示结束位置

运行结果：