递归方法思想

递归算法基础

在计算机编程应用中，递归算法对解决大多数问题都是十分有效的，主要是因为它能够使算法的描述变得简洁和易于理解，主要有3个特点。

• 递归过程一般通过函数或子过程来实现
• 递归算法在函数或子过程的内部，直接或间接地调用自己的算法。
• 递归算法实际上是把问题转化成规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解。

使用递归算法时，应该注意以下4点：

• 递归是在过程或者函数中调用自身的过程
• 在使用递归策略时，必须有一个明确的递归结束条件，称之为递归出口
• 递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡使用
• 在递归调用过程中，系统通过栈来存储每一层的返回点和局部量。如果递归次数过多，很容易造成栈溢出(StackOverflowError)

例如：

public class stack {
    private static int index = 1;
    public static void main(String[] args) {
        try {
            test();
        } catch (StackOverflowError e) {
            System.out.println(index);
            e.printStackTrace();
        }
    }
    public static void test() {
        index++;
        test();
    }
}

通过递归不断地去调用自身，超过系统的栈的深度就会直接报错

接下来通过汉诺塔的例子具体讲解一下递归过程
首先什么是汉诺塔呢？
在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
okay，我们的目标是要把第一个柱子上的64片移到第三个柱子上面去

• 首先第一轮可以把前63片移到第二个柱子上面去，再把第64片移到第三个柱子上面去，再把第二个柱子上面的63片移到第三个柱子上面
• 那么，第二轮的问题是怎么把前63片移到第二个柱子，可以先把前62片移到第三个柱子上面去，再把第63片移到第二个柱子上面去，再把第三个柱子上面的62片移到第二个柱子上面
• .......
• 到了最上面一片只需要将第一片移开，把第二片移到另一个空柱子，再把第一片移到第二片上面去，完成整个操作(第一片移到哪个柱子取决于你的片数的奇偶)

这样就形成了递归，在你调用move(n,a,b,c)的时候，只需要让n-1个片移到b上面去(move(n-1,a,c,b))，再把第n个片移到c，紧接着把b上面的n-1个片移到c上面去(move(n-1,b,a,c))，就可以完成整个操作。
从结果上面来看，需要搬移的次数为2^n - 1

public class HanoiTest {
    private static int count;
    public static void main(String[] args) {
        move(64,'a','b','c');
        System.out.println(count);
    }
    private static  void move(int n,int a,int b,int c) {
        if (n == 1) {
            count++;
            System.out.println((char)a +"-->"+ (char)c);
        } else {
            move(n-1,a,c,b);
            count++;
            System.out.println((char)a +"-->"+ (char)c);
            move(n-1,b,a,c);
        }
    }
}