# 第17节 认识一些经典递归过程
# 暴力递归
暴力递归就是尝试
- 把问题转化为规模缩小了的同类问题的子问题
- 有明确的不需要继续进行递归的条件(base case)
- 有当得到了子问题的结果之后的决策过程
- 不记录每一个子问题的解
# 熟悉什么叫尝试？
打印n层汉诺塔从最左边移动到最右边的全部过程
代码：
package class17;
public class Test {
/**
* 1-n 层 汉诺塔问题
* 1、2、3在left塔 移动最小次数将移至right塔
* 原则是小值压着大值
* 使用递归过程 使用六个函数 不优化
* @param n
*/
public static void hannuo1(int n) {
if(n < 1) {
return ;
}
leftToRight(n);
}
/**
* 1、将n-1由left移到mid
* 2、将n移入right 打印
* 3、将n-1由mid移动right
* @param n
*/
private static void leftToRight(int n) {
if(n == 1) {
System.out.println("move " + n + " left to right.");
return;
}
leftToMid(n - 1);
System.out.println("move " + n + " left to right.");
midToRight(n - 1);
}
/**
* 1、将n-1由mid移到right
* 2、将n移入left 打印
* 3、将n-1由right移动left
* @param n
*/
private static void midToLeft(int n) {
if(n == 1) {
System.out.println("move " + n + " mid to left.");
return;
}
midToRight(n - 1);
System.out.println("move " + n + " mid to left.");
rightToLeft(n - 1);
}
/**
* 1、将n-1由right移到left
* 2、将n移入mid 打印
* 3、将n-1由left移动mid
* @param n
*/
private static void rightToMid(int n) {
if(n == 1) {
System.out.println("move " + n + " right to mid.");
return;
}
rightToLeft(n - 1);
System.out.println("move " + n + " right to mid.");
leftToMid(n - 1);
}
/**
* 1、将n-1由mid移到left
* 2、将n移入right 打印
* 3、将n-1由left移动right
* @param n
*/
private static void midToRight(int n) {
if(n == 1) {
System.out.println("move " + n + " mid to right.");
return;
}
midToLeft(n - 1);
System.out.println("move " + n + " mid to right.");
leftToRight(n - 1);
}
/**
* 1、将n-1由left移到right
* 2、将n移入mid 打印
* 3、将n-1由right移动mid
* @param n
*/
private static void leftToMid(int n) {
if(n == 1) {
System.out.println("move " + n + " left to mid.");
return;
}
leftToRight(n - 1);
System.out.println("move " + n + " left to mid.");
rightToMid(n - 1);
}
/**
* 1、将n-1由right移到mid
* 2、将n移入left 打印
* 3、将n-1由mid移动left
* @param n
*/
private static void rightToLeft(int n) {
if(n == 1) {
System.out.println("move " + n + " right to left.");
return;
}
rightToMid(n-1);
System.out.println("move " + n + " right to left.");
midToLeft(n-1);
}
/**
* 1-n 层 汉诺塔问题
* 1、2、3在from塔 移动最小次数将移至to塔
* 原则是小值压着大值
* 使用递归过程 使用一个函数 加入参数 改变递归过程
* @param n
*/
public static void hannuo2(int n) {
if(n < 1) {
return ;
}
process(n, "left", "right", "mid");
}
/**
* 1、将n-1由from移到other
* 2、将n移入to 打印
* 3、将n-1由other移动to
* @param n
* @param from
* @param to
* @param other
*/
private static void process(int n, String from, String to, String other) {
if(n == 1) {
System.out.println("move " + n + " " + from + " to " + to + ".");
return ;
}
process(n - 1, from , other, to);
System.out.println("move " + n + " " + from + " to " + to + ".");
process(n - 1, other , to, from);
}
public static void main(String[] args) {
hannuo1(3);
System.out.println("==================================================");
hannuo2(3);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
打印一个字符串的全部子序列
代码：
package class17;
public class Test {
/**
* 打印一个字符串的全部子序列
* @param s
*/
public static void printSubSequence(String s) {
if(s == null || s.length() == 0) {
return;
}
char[] str = s.toCharArray();
List<String> ans = new ArrayList<>();
int index = 0;
String path = "";
process(str, index, path, ans);
for(String ss : ans) {
System.out.println(ss);
}
}
/**
* 递归过程
* @param str 固定参数
* @param index 当前位置
* @param path 已经决策的字符序列了
* @param ans 字符子序列的结果
*/
private static void process(char[] str, int index, String path, List<String> ans) {
if(index == str.length) {
// 当前位置来到了结束
ans.add(path);
return;
}
// 不要当前位置的字符
process(str, index + 1, path, ans);
// 要当前位置的字符
process(str, index + 1, path + String.valueOf(str[index]), ans);
}
public static void main(String[] args) {
printSubSequence("abcc");
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
打印一个字符串的全部子序列
要求不要出现重复字面值的子序列
代码：
package class17;
public class Test {
/**
* 打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
* @param s
*/
public static void printSubSequenceNoRepeat(String s) {
if(s == null || s.length() == 0) {
return ;
}
char[] str = s.toCharArray();
HashSet<String> ans = new HashSet<>();
int index = 0;
String path = "";
process(str, index, path , ans);
String[] strArray = new String[ans.size()];
ans.toArray(strArray);
for(String ss : strArray) {
System.out.println(ss);
}
}
/**
* 递归过程
* @param str 固定参数
* @param index 当前位置
* @param path 已经决策的字符序列了
* @param ans 字符子序列的结果
*/
private static void process(char[] str, int index, String path, HashSet<String> ans) {
if(index == str.length) {
ans.add(path);
return;
}
process(str, index + 1, path, ans);
process(str, index + 1, path + String.valueOf(str[index]), ans);
}
public static void main(String[] args) {
printSubSequenceNoRepeat("abcc");
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
打印一个字符串的全部排列
代码：
package class17;
public class Test {
/**
* 打印一个字符串的全部排列
* 不优化版本
* @param s
*/
public static void printAllCombination1(String s) {
if(s == null || s.length() == 0) {
return ;
}
char[] str = s.toCharArray();
List<String> yuList = new ArrayList<>();
for(char c : str) {
yuList.add(String.valueOf(c));
}
String path = "";
List<String> ans = new ArrayList<>();
process(yuList, path, ans);
for(String ss : ans) {
System.out.println(ss);
}
}
/**
* 递归过程
* @param yuList 剩余字符可以用于排列的
* @param path 已经排列好的
* @param ans 答案
*/
private static void process(List<String> yuList, String path, List<String> ans) {
if(yuList.isEmpty()) {
ans.add(path);
return ;
}
for(int i = 0; i < yuList.size(); i++) {
String str = yuList.get(i);
yuList.remove(i);
process(yuList, path + str, ans);
yuList.add(i, str);
}
}
public static void main(String[] args) {
printAllCombination1("abcc");
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
打印一个字符串的全部排列
要求不要出现重复的排列
代码：
package class17;
public class Test {
/**
* 打印一个字符串的全部排列
* 优化版本 并且去重
* @param s
*/
public static void printAllCombination2(String s) {
if(s == null || s.length() == 0) {
return ;
}
char[] str = s.toCharArray();
List<String> ans = new ArrayList<>();
process(str, 0, ans);
for(String ss: ans) {
System.out.println(ss);
}
}
/**
* 递归过程
* @param str
* @param index
* @param ans
*/
private static void process(char[] str, int index, List<String> ans) {
if(index == str.length) {
ans.add(String.valueOf(str));
return ;
}
boolean[] visit = new boolean[256];
// 加入visit 验证每个位置上的字符不能重复命中
for(int i = index; i < str.length; i++) {
if(!visit[str[i]]) {
visit[str[i]] = true;
swap(str, i , index);
process(str, index + 1, ans);
swap(str, i , index);
}
}
}
private static void swap(char[] str, int i, int j) {
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
public static void main(String[] args) {
printAllCombination2("abcc");
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
将字符串的全部排列及其全部子序列打印
要求不要出现重复的排列
要求不要出现重复字面值的子序列
代码：
package class17;
public class Test {
/**
* 将字符串的全部排列及其全部子序列打印，就是暴力破解密码的过程
* 要求不要出现重复的排列
* 要求不要出现重复字面值的子序列
* @param s
*/
public static HashMap<Integer, List<String>> printAllCombAndSeq(String s) {
if(s == null || s.length() == 0) {
return null;
}
char[] str = s.toCharArray();
// 存放所有不重复的排列答案
HashSet<String> ansSet = new HashSet<>();
int index = 0;
//解决全部排列问题 使用替换char[]位置的方式 从i位置开始到最后依次替换
f(str, index, ansSet);
String[] strArray = new String[ansSet.size()];
ansSet.toArray(strArray);
// 存放以长度为区分的答案
HashMap<Integer, List<String>> ansMap = new HashMap<>();
int ssLen = 0;
List<String> ansList = null;
for(String ss : strArray) {
ssLen = ss.length();
if(ansMap.containsKey(ssLen)) {
ansMap.get(ssLen).add(ss);
} else {
ansList = new ArrayList<>();
ansList.add(ss);
ansMap.put(ssLen, ansList);
}
System.out.println(ss);
}
return ansMap;
}
/**
* 递归过程
* @param str 字符序列
* @param index 当前的位置 在0-index上已经排列好
* @param ansSet 所有排列及子序列的答案记录
*/
private static void f(char[] str, int index, HashSet<String> ansSet) {
if(index == str.length) {
ansSet.add(String.valueOf(str));
// 得到所有子序列
g(str, 0, "", ansSet);
return ;
}
boolean[] visiti = new boolean[256];
for(int i = index; i < str.length; i++) {
if(!visiti[str[i]]) {
visiti[str[i]] = true;
swap(str, i, index);
f(str, index + 1, ansSet);
swap(str, i, index);
}
}
}
/**
* @param str 字符序列
* @param index 当前位置
* @param path 已经确定的结果
* @param ansSubSet 记录结果
*/
private static void g(char[] str, int index, String path, HashSet<String> ansSubSet) {
if(index == str.length) {
ansSubSet.add(path);
return;
}
// 不要index上的字符
g(str, index + 1, path, ansSubSet);
// 要index上的字符
g(str, index + 1, path + String.valueOf(str[index]), ansSubSet);
}
public static void main(String[] args) {
printAllCombAndSeq("abcff");
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
破解密码穷举法
给定一个
char[]字符选择范围，
String pwd原密码
int low密码的最低长度
int high密码的最高长度穷举所有可能的密码与原密码比对是否相等
时间复杂度为
O(char[].size * high-low * high)，所以得出结论密码设置时尽量字符选择范围要广
密码长度要长
代码：
package class17;
public class Test {
/**
* 破解密码穷举法
* @param range
* @param pwd
* @param low
* @param high
*/
public static void crakThePwd(char[] range, String pwd, int low, int high) {
if(pwd == null || range == null || pwd.length() == 0 || range.length == 0
|| low < 1 || high < 1 || low > high) {
return;
}
HashSet<String> ansSet = new HashSet<>();
// 从low位到high依次穷举字符
for(int curLen = low; curLen <= high; curLen++) {
// 递归过程
process(range, 0, curLen, "", ansSet);
}
String[] list = new String[ansSet.size()];
ansSet.toArray(list);
for(String ss : list) {
System.out.println(ss);
}
}
/**
* 当前
* @param range 字符的选择范围
* @param index 当前位置
* @param curLen 当前密码长度
* @param path
* @param ansSet
*/
private static void process(char[] range, int index, int curLen, String path, HashSet<String> ansSet) {
if(index == curLen) {
ansSet.add(path);
return;
}
// range里的所有字符 都有可能要
for(char c : range) {
process(range, index + 1, curLen, path + String.valueOf(c), ansSet);
}
}
public static void main(String[] args) {
char[] range = new char[] {'1','2'};
crakThePwd(range, "12323", 5, 8);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
给你一个栈，请你逆序这个栈， 不能申请额外的数据结构， 只能使用递归函数。 如何实现?
利用系统栈，递归过程就是将函数变量压入系统栈
代码：
package class17;
public class Test {
/**
* 反转栈结构
* @param stack
*/
public static void reversalStack(Stack<Integer> stack) {
if(stack.isEmpty()) {
return ;
}
Integer ans = f(stack);
reversalStack(stack);
stack.push(ans);
}
/**
* 从栈底弹出
* 上面的元素盖下来 利用系统栈 作为倒栈
* @param stack
*/
private static int f(Stack<Integer> stack) {
Integer ans = stack.pop();
if(stack.isEmpty()) {
return ans;
} else {
Integer last = f(stack);
stack.push(ans);
return last;
}
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<Integer>();
stack.add(1);
stack.add(2);
stack.add(3);
System.out.println("原始的顺序：");
while(!stack.isEmpty()) {
System.out.println(stack.pop());
}
stack.add(1);
stack.add(2);
stack.add(3);
System.out.println("逆向的顺序：");
reversalStack(stack);
while(!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53