Java递归问题--汉诺塔，终于懂了..._汉诺塔会暴栈吗

什么是递归

当一个方法不断调用自己就是递归，不断递归，不断套娃，直到递归遇到终止条件开始回溯，最终结束程序。

public class DiGui {
    public static void main(String[] args) {
        begin();
    }
    public static void begin(){
        System.out.println("开始套娃");
        begin();
        //当没有终止条件，将不会执行以下代码
        //在递归以下的所有内容都要等待递归完成后才能执行
        System.out.println("程序结束");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

我们在编写递归时一定不能忘记，终止条件，否则无限的调用自己会出现栈内存溢出的情况.
有中止条件不代表不会发生栈溢出，如果递归的太深仍然会出现栈内存溢出的情况，这时候可以排查问题，检查中止条件，扩大栈内存(java -Xss)，或者不使用递归解决问题.

什么是汉诺塔问题

有A,B,C三个柱子,A上有铜片64片,需要我们移动铜片到C柱子上,且移动过程中和移动后的铜片保持上小下大的规则.

简单演示

使用递归分析

使用递归，先思考它的终止条件，如果只有一块的时候，就直接移动

我们知道n=1怎么挪动木块，也知道n=2时怎么挪动木块
那么当n=3甚至更多时，我们可以将它类比分成n和（n-1）两个部分去思考。

思路

把这个需要创建的方法想象成题目，n层木块从A–>C，中间B柱子作为辅助
han(int n,char A,char B,char C)

按照我们分析的解题步骤应该是这样子滴：
1.首先要将（n-1）从A挪到B
2.将n从A挪到C
3.将（n-1）从B挪到C

那么问题是如何将（n-1）从A挪到B <==> 等价于出了一道新的汉诺塔题

han(n-1,A,C,B)

这个时候我们调用它本身的方法直到n=1时开始回溯

public class DiGui {
    public static void main(String[] args) {
        han(3,'A','B','C');
    }
    public static void han(int n,char A,char B,char C){
        //把这个方法想象成题目，n层木块从A-->C，中间B柱子作为辅助
        if (n==1){
            mov(1,A,C);
        }else {
            han(n-1,A,C,B);
            mov(n,A,C);
            han(n-1,B,A,C);
        }
    }
    public static void mov(int n,char A,char B){
        System.out.println("当前木块"+n+"从"+A+"——>"+B+"...");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

输出结果

总结

写递归的两部分：终止条件，递归逻辑
用方法描述题目，那么这个方法就代表这个题目
将题目拆解为若干子问题，将相同的逻辑提取出来，写在描述题目的方法中
这个题目里面的子问题 就相当于 这个方法里调用它的方法

不断学习，不断进步，加油ヾ(◍°∇°◍)ﾉﾞ