关于算法:从-最具启发性的汉诺塔问题开始-聊递归

本文篇幅较长，倡议认真急躁看完，置信会有极大的播种。

有三根杆子 A，B，C。A 杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上顺次变小。要求按下列规定将所有圆盘移至 C 杆：每次只能挪动一个圆盘；大盘不能叠在小盘下面。

问：起码要挪动多少次？并打印每次挪动的状况。

咱们的指标是将 1、2、3 圆盘 从左杆移到右杆 上

能够拆解为以下三步

1）（大步）将 1、2 圆盘 从左移到中杆 上

2）将 3 圆盘 从左移到右杆 上

3）（大步）将 1、2 圆盘从 中移到右杆 上

代码如下：

/**
 * @author Java 和算法学习：周一
 */
public static void leftToRight(int n) {if (n == 1) { // base case
        System.out.println("Move 1 from left to right");
        return;
    }
    // 1、1 到 n - 1 个圆盘从左到中
    leftToMid(n - 1);
    // 2、从左到右
    System.out.println("Move" + n + "from left to right");
    // 3、1 到 n - 1 个圆盘从中到右
    midToRight(n - 1);
}

整个左到右办法，你会发现第一大步依赖 左到中 子办法，第三大步依赖 中到右 子办法，而后你去补起左到中办法、中到右办法；此时又会发现左到中依赖左到右、右到中办法，中到右依赖中到左、左到右办法……

/**
 * @author Java 和算法学习：周一
 */
private static void leftToMid(int n) {if (n == 1) {System.out.println("Move 1 from left to mid");
        return;
    }
    leftToRight(n - 1);
    System.out.println("Move" + n + "from left to mid");
    rightToMid(n - 1);
}

private static void midToRight(int n) {if (n == 1) {System.out.println("Move 1 from mid to right");
        return;
    }
    midToLeft(n - 1);
    System.out.println("Move" + n + "from mid to right");
    leftToRight(n - 1);
}

private static void rightToMid(int n) {if (n == 1) {System.out.println("Move 1 from right to mid");
        return;
    }
    rightToLeft(n - 1);
    System.out.println("Move" + n + "from right to mid");
    leftToMid(n - 1);
}

private static void midToLeft(int n) {if (n == 1) {System.out.println("Move 1 from mid to left");
        return;
    }
    midToRight(n - 1);
    System.out.println("Move" + n + "from mid to left");
    rightToLeft(n - 1);
}

private static void rightToLeft(int n) {if (n == 1) {System.out.println("Move 1 from right to left");
        return;
    }
    rightToMid(n - 1);
    System.out.println("Move" + n + "from right to left");
    midToLeft(n - 1);
}

最初你会发现 左到中、左到右、中到左、中到右、右到左、右到中 这 6 个办法相互依赖实现了汉诺塔问题。

是不是有点神奇，递归有时候是有点玄学，然而只有把子过程想明确，base case 写对，就跑进去了（同时，须要有一点 宏观思维）。

这 6 个过程，是不是有点麻烦，同时仔细的搭档可能也发现了，这 6 个办法是及其类似的，那么咱们是不是能够定义 from、to、other 三个变量，他们都能够示意左、中、右。当我左到右时，from= 左、to= 右、other= 中；当左到中时，from= 左、to= 中、other= 右……是不是就能 六合一号召神龙 了。

同样拆解为以下三步

1）（大步）将 1、2 圆盘（即下面 n - 1 个圆盘）从左移到中杆 上

2）将 3 圆盘（即最大的圆盘）从左移到右杆 上

3）（大步）将 1、2 圆盘（即下面 n - 1 个圆盘）从中移到右杆 上

/**
 * 第一次调用 function 时：from= 左、to= 右、other= 中
 * 示意借助 other= 中，将圆盘从 from= 左挪动到 to= 右杆上
 *
 * @author Java 和算法学习：周一
 *
 * @param n     总共的圆盘数量
 * @param from  起始地位
 * @param to    指标地位
 * @param other 残余杆子
 */
public static void function(int n, String from, String to, String other) {if (n == 1) {System.out.println("Move 1 from" + from + "to" + to);
        return;
    }
    // 1. 将下面 n - 1 个圆盘从左移到中杆上，// 即起始地位为左，以后 from= 左；指标地位中，以后 other= 中
    function(n - 1, from, other, to);
    // 2. 将最大的圆盘从左移到右杆上
    System.out.println("Move" + n + "from" + from + "to" + to);
    // 3. 将下面 n - 1 个圆盘从中移到右杆上
    // 即起始地位为中，以后 other= 中；指标地位右，以后 to= 右
    function(n - 1, other, to, from);
}

这时候，咱们就学会了一个技巧，一个递归函数能够通过减少参数的形式表白更多的可能性，听着跟废话一样，然而当初你再品品。

然而，若没有后面启发性的过程，间接看这个是不是有点难懂；有了启发性的过程，再看是不是恍然大悟。

是不是发现上课时听老师讲汉诺塔时一头雾水，要是老师过后能这么讲相对听的明明白白。此处应有掌声（和点赞）。

零打碎敲，再来看看几个递归过程。

对于字符串 ”12345″，任意取其中 0 个、1 个、2 个、3 个、4 个、5 个都是它的子序列，同时绝对程序不能扭转。

对于字符串“123”，咱们能够很容易剖析出以下递归过程

/**
 * @author Java 和算法学习：周一
 */
public static List<String> getAllSubSequences(String s) {char[] str = s.toCharArray();
    List<String> answer = new ArrayList<>();
    String path = "";
    process1(str, 0, answer, path);
    return answer;
}

/**
 * 以后来到了 str[index]字符
 * str[0..index-1]曾经走过了，之前的抉择都在 path 上，之前的抉择曾经不能扭转了，就是 path。* 然而 str[index....]还能自由选择，把 str[index....]所有生成的子序列，放入到 answer 里
 *
 * @param str    指定的字符串（固定）* @param index  以后所处的地位
 * @param answer 之前决策依据产生的答案
 * @param path   之前曾经做的抉择
 */
public static void process1(char[] str, int index, List<String> answer, String path) {
    // 以后来到了字符串的最初地位，曾经不能再做决策了，answer 只能放入之前的决策
    if (index == str.length) {answer.add(path);
        return;
    }
    // 以后没有要 index 地位的字符
    process1(str, index + 1, answer, path);
    // 以后要 index 地位的字符
    process1(str, index + 1, answer, path + str[index]);
}

process1 办法就是下面剖析进去的递归过程。

打印一个字符串的全副子序列，要求没有反复字面值的子序列，间接将下面的 List 换成 Set 即可去重。

/**
 * 打印一个字符串的全副子序列，要求没有反复字面值的子序列
 *
 * @author Java 和算法学习：周一
 */
public static Set<String> getAllSubSequencesNoRepeat(String s) {char[] str = s.toCharArray();
    Set<String> answer = new HashSet<>();
    String path = "";
    process2(str, 0, answer, path);
    return answer;
}

public static void process2(char[] str, int index, Set<String> answer, String path) {if (index == str.length) {answer.add(path);
        return;
    }
    process2(str, index + 1, answer, path);
    process2(str, index + 1, answer, path + str[index]);
}

所有字符都要，只是程序不同。

在第一大列抉择 a 时，造成了一些后果，当我进行第二大列递归时，得把 a 增加回去，放弃最开始的 abc，在第二大列抉择 b 时进行递归失去的后果才是正确的，对于每一列的每一位抉择都是如此，递归完结后要复原现场。

/**
 * 1. 增加删除的形式
 *
 * @author Java 和算法学习：周一
 */
public static List<String> permutation1(String s) {List<String> answer = new ArrayList<>();
    if (s == null || s.length() == 0) {return answer;}

    ArrayList<Character> strList = new ArrayList<>();
    for (char c : s.toCharArray()) {strList.add(c);
    }
    String path = "";
    process1(strList, path, answer);

    return answer;
}

/**
 * 递归获取全排列
 *
 * @param strList 以后参加抉择的所有字符
 * @param path 之前所做的抉择
 * @param answer 最终后果
 */
private static void process1(ArrayList<Character> strList, String path, List<String> answer) {
    // 以后没有能够抉择的字符了，answer 只能放入之前的抉择
    if (strList.isEmpty()) {answer.add(path);
        return;
    }
    for (int i = 0; i < strList.size(); i++) {
        // 以后抉择的字符
        char cur = strList.get(i);
        // 舍弃曾经抉择的字符
        strList.remove(i);
        // 残余字符再进行抉择
        process1(strList, path + cur, answer);
        // 复原现场
        strList.add(i, cur);
    }
}

在第一大列造成后果 acb 时，如果不复原现场，当我进行第二大列递归时，是从 acb 开始进行 0、1 位替换造成 cab，和前面的反复了，所以每一步替换递归完结后 要复原现场。

/**
 * 2. 替换的形式
 *
 * @author Java 和算法学习：周一
 */
public static List<String> permutation2(String s) {List<String> answer = new ArrayList<>();
    if (s == null || s.length() == 0) {return answer;}
    char[] str = s.toCharArray();
    process2(str, 0, answer);
    return answer;
}

/**
 * 递归获取全排列
 *
 * @param str 以后经验过替换后的字符
 * @param index 以后替换到哪个地位了
 * @param answer 后果
 */
private static void process2(char[] str, int index, List<String> answer) {
    // 以后来到了字符串的最初地位，曾经不能再替换了，answer 只能放入之前替换后的字符
    if (index == str.length) {answer.add(String.valueOf(str));
        return;
    }

    // index 之前的曾经替换过不能再变了，所以从 index 往后还能够再替换
    for (int i = index; i < str.length; i++) {
        // index、i 地位替换
        swap(str, index, i);
        // index 前面的持续替换
        process2(str, index + 1, answer);
        // index、i 地位 复原现场
        swap(str, index, i);
    }
}

/**
 * 替换的形式，去重
 *
 * @author Java 和算法学习：周一
 */
public static List<String> permutation3(String s) {List<String> answer = new ArrayList<>();
    if (s == null || s.length() == 0) {return answer;}
    char[] str = s.toCharArray();
    process3(str, 0, answer);
    return answer;
}

/**
 * 递归获取全排列，没有反复的字符串
 *
 * @param str 以后经验过替换后的字符
 * @param index 以后替换到哪个地位了
 * @param answer 后果
 */
private static void process3(char[] str, int index, List<String> answer) {
    // 以后来到了字符串的最初地位，曾经不能再替换了，answer 只能放入之前替换后的字符
    if (index == str.length) {answer.add(String.valueOf(str));
        return;
    }

    boolean[] visited = new boolean[256];
    // index 之前的曾经替换过不能再变了，所以从 index 往后还能够再替换
    for (int i = index; i < str.length; i++) {// str[i]地位对应字符没有呈现过才递归替换，否则疏忽
        if (!visited[str[i]]) {visited[str[i]] = true;
            // index、i 地位替换
            swap(str, index, i);
            // index 前面的持续替换
            process3(str, index + 1, answer);
            // index、i 地位 复原现场
            swap(str, index, i);
        }
    }
}

认真看以上代码，发现没有再用 Set 的办法来去重，为啥？

因为采纳 Set 去重，程序会反复的做很多雷同字符的递归操作，将产生的雷同字符串放到 Set 中由 Set 去重；而采纳以上形式，对于雷同的字符就不会再反复的递归了，无效缩小了反复分支的递归操作，俗称剪枝。

相当于 Set 是从后果中过滤去重，而以上形式是在中途的过程就曾经去重了。

给你一个栈，请你逆序这个栈，不能申请额定的数据结构，只能应用递归函数。如何实现?

/**
 * 失去栈底元素，残余元素间接下沉
 *
 * 例如，从栈顶到栈底元素为 1、2、3、4、5
 * 此办法返回 5，残余从栈顶到栈底元素为 1、2、3、4
 *
 * @author Java 和算法学习：周一
 */
private static int getDown(Stack<Integer> stack) {int result = stack.pop();
    if (stack.isEmpty()) {return result;} else {int last = getDown(stack);
        stack.push(result);
        return last;
    }
}

/**
 * @author Java 和算法学习：周一
 */
public static void reverse(Stack<Integer> stack) {if (stack.isEmpty()) {return;}
    int down = getDown(stack);
    reverse(stack);
    stack.push(down);
}

本文所有代码

Github 地址：https://github.com/monday-pro/algorithm-study/tree/master/src/basic/dynamicprogramming/recursion

Gitee 地址：https://gitee.com/monday-pro/algorithm-study/tree/master/src/basic/dynamicprogramming/recursion

怎么样，是不是如沐春风般醍醐灌顶。

关于算法:从-最具启发性的汉诺塔问题开始-聊递归

一、最具启发性的汉诺塔问题

1、汉诺塔问题形容

2、从最后开始

3、优化

二、打印一个字符串的全副子序列

1、子序列定义

2、代码

三、打印一个字符串的全副子序列，没有反复值

四、打印一个字符串的全副全排列

1、全排列定义

2、采纳舍弃增加的形式

（1）递归过程如下

（2）代码

3、始终在原始字符串上以替换的形式进行递归

（1）递归过程如下

（2）代码

五、打印一个字符串的全副全排列，没有反复值

1、代码

2、为啥咱们不采纳 Set 的形式来去重？

六、栈的逆序

1、失去栈底元素

（1）代码

（2）过程

2、递归逆序

（1）代码

（2）过程