本文篇幅较长，倡议认真急躁看完，置信会有极大的播种。
一、最具启发性的汉诺塔问题
1、汉诺塔问题形容
有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上顺次变小。要求按下列规定将所有圆盘移至 C 杆：每次只能挪动一个圆盘；大盘不能叠在小盘下面。
问：起码要挪动多少次？并打印每次挪动的状况。
2、从最后开始
咱们的指标是将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写对，就跑进去了（同时，须要有一点宏观思维）。
3、优化
这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);
}
这时候，咱们就学会了一个技巧，一个递归函数能够通过减少参数的形式表白更多的可能性，听着跟废话一样，然而当初你再品品。
然而，若没有后面启发性的过程，间接看这个是不是有点难懂；有了启发性的过程，再看是不是恍然大悟。
是不是发现上课时听老师讲汉诺塔时一头雾水，要是老师过后能这么讲相对听的明明白白。此处应有掌声（和点赞）。
零打碎敲，再来看看几个递归过程。
二、打印一个字符串的全副子序列
1、子序列定义
对于字符串”12345″，任意取其中0个、1个、2个、3个、4个、5个都是它的子序列，同时绝对程序不能扭转。
对于字符串“123”，咱们能够很容易剖析出以下递归过程
2、代码
/**
* @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]);
}
四、打印一个字符串的全副全排列
1、全排列定义
所有字符都要，只是程序不同。
2、采纳舍弃增加的形式
（1）递归过程如下
在第一大列抉择a时，造成了一些后果，当我进行第二大列递归时，得把a增加回去，放弃最开始的abc，在第二大列抉择b时进行递归失去的后果才是正确的，对于每一列的每一位抉择都是如此，递归完结后要复原现场。
（2）代码
/**
* 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);
}
}
3、始终在原始字符串上以替换的形式进行递归
在第一大列造成后果acb时，如果不复原现场，当我进行第二大列递归时，是从acb开始进行0、1位替换造成cab，和前面的反复了，所以每一步替换递归完结后要复原现场。
（1）递归过程如下
（2）代码
/**
* 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);
}
}
五、打印一个字符串的全副全排列，没有反复值
1、代码
/**
* 替换的形式，去重
*
* @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);
}
}
}
2、为啥咱们不采纳Set的形式来去重？
认真看以上代码，发现没有再用Set的办法来去重，为啥？
因为采纳Set去重，程序会反复的做很多雷同字符的递归操作，将产生的雷同字符串放到Set中由Set去重；而采纳以上形式，对于雷同的字符就不会再反复的递归了，无效缩小了反复分支的递归操作，俗称剪枝。
相当于Set是从后果中过滤去重，而以上形式是在中途的过程就曾经去重了。
六、栈的逆序
给你一个栈，请你逆序这个栈，不能申请额定的数据结构，只能应用递归函数。如何实现?
1、失去栈底元素
（1）代码
/**
* 失去栈底元素，残余元素间接下沉
*
* 例如，从栈顶到栈底元素为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;
}
}
（2）过程
2、递归逆序
（1）代码
/**
* @author Java和算法学习：周一
*/
public static void reverse(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
int down = getDown(stack);
reverse(stack);
stack.push(down);
}
（2）过程
本文所有代码
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
怎么样，是不是如沐春风般醍醐灌顶。
发表回复