递归算法

问题1：给定不重复的字符串，如123，给出全排列

分析：算123的全排列，首先算以1开头的23的全排列，然后再算以2开头的13的全排列，依次类推。
可以在循环里每次和开头的字符调换位置，然后对剩下的字符串全排列，每轮剩下的全排列完后输出即可，由于前面字符串的位置调换了，因此每轮结束后要把位置还原。

public static void main(String[] args) {
        StringBuilder str = new StringBuilder("123");
        StringFullPermutation stringFullPermutation = new StringFullPermutation();
        stringFullPermutation.fullPermutation(str, 0, str.length());
    }

    /**
     * 递归
     * @param str
     */
    public void fullPermutation(StringBuilder str, int from, int to){
        if(from == to){
            System.out.println(str.toString());
        }
        /**
         *
         */
        for (int i = from; i < to; i++) {
//            System.out.println("调换位置" + str.charAt(from) + ", " + str.charAt(i));
//            from想象是0，每次循环把i位置的数字和from(0)的位置对调
            swap(str, from, i);
            System.out.println("首字母是" + str.charAt(from) + "，算" + str.substring(from + 1, to) + "的全排列");
//            算1开头的2和3全排列，
            this.fullPermutation(str, from + 1, to);//注意：这里是from+1，不是i+1
//            System.out.println("还原位置" + str.charAt(i) + ", " + str.charAt(from));
//          算完1开头的全排列后，再把1放到开头， 即每轮全排列后都要使字符串回到最初的“123”状态
            swap(str, i, from);
        }
    }

    private void swap(StringBuilder str, int i, int j){
        char c = str.charAt(i);
        str.setCharAt(i, str.charAt(j));
        str.setCharAt(j, c);
    }

问题2：汉诺塔问题，3个柱子，1、2、3， 把ABC（A>B>C）3块圆盘从1柱移到3柱，要求大圆盘不能放在小圆盘上面，每次只能移动一块圆盘。
分析：如果一开始就陷入细节怎么移动，这个问题不好解决。可以先从大的范围思考，如果把BC从1柱移到2柱（先不要考虑怎么把BC移到2柱），然后把A从1柱移到3柱，再把BC从2柱移到3柱就可以了，这个思路够简单，那接下来的问题就是解决怎么把BC移到2柱，发现这和原始问题很像，只是比原始问题简单了，那就可以一直这么简单的拆解下去，这种思想也就是递归。

  public static void main(String[] args) {
        HanoiTower hanoiTower = new HanoiTower();
        //3个柱子，1、2、3， 把ABC（A>B>C）3块圆盘从1柱移到3柱，要求大圆盘不能放在小圆盘上面
        hanoiTower.move("ABC", 0, "1", "2", "3");
    }

/**
* @parameter middle 辅助柱子
**/
    public void move(String str, int index, String from, String middle, String to){
        if(index >= str.length()){
            return;
        }
        this.move(str, index + 1, from, to, middle);
        System.out.println("移动" + str.charAt(index) + "从" + from + "柱到" + to + "柱");
        this.move(str, index + 1, middle, from, to);
    }

总结：
递归算法说费脑是真费脑，说不费脑真不费脑，在开始写的时候按分治思想递归写完即可，至于每轮递归的细节先不要考虑，不然会掉入细节的坑里。

递归算法的时间复杂度是：
f(n)=nf(n-1)=n(n-1)f(n-2)...
依次类推：f(n)=n(n-1)(n_2)...1 也就是n!,这个还是很恐怖的，所以尽量不用递归