递归
递归基础与递归的宏观语义
本质上，将原来的问题，转化为更小的同一问题
举例：数组求和
1
2
3
4sum(arr[0...0-1]) = arr[0] + summ(arr[1...n-1]) -- 更小的同一问题
sum(arr[1...n-1]) = arr[1] + summ(arr[2...n-1]) -- 更小的同一问题
......
sum(arr[n-1...n-1]) = arr[n-1] + summ([]) -- 最基本的问题代码实现
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
39package demo.recursion;
/**
* 递归求和
*
* @author jingLv
* @date 2020/12/14
*/
public class SumForRecursion {
/**
* 递归求arr中所有元素的和
*
* @param arr 数组
* @return 求和的值
*/
public static int sum(int[] arr) {
return sum(arr, 0);
}
/**
* 计算arr[l...n)这个区间内所有数字的和
*
* @param arr 数组
* @param l 数组的起始值（左边界的索引值）
* @return 求和的值
*/
private static int sum(int[] arr, int l) {
if (l == arr.length) {
return 0;
}
return arr[l] + sum(arr, l + 1);
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5, 6, 7, 8};
System.out.println(sum(nums));
}
}注意递归函数的“宏观”语义，例如上面的的例子，宏观语义是：计算arr[l…n)这个区间内所有数字的和
递归函数就是一个函数，完成一个功能
递归算法基本原则
- 求解最基本问题
- 把原问题转化成更小的问题
链表和递归
链表具有天然的递归性
我们通过“leetcode203题，删除链表中的元素”来看链表的递归性
ListNode
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
58package demo.recursion;
/**
* 定义ListNode，在leetcode203题中使用
*
* @author jingLv
* @date 2020/12/14
*/
public class ListNode {
/**
* 值
*/
int val;
/**
* 节点
*/
ListNode next;
ListNode(int x) {
val = x;
}
/**
* 链表节点的构造函数
* 使用arr为参数，创建一个链表，当前的ListNode为链表头节点
*
* @param arr 数组
*/
public ListNode(int[] arr) {
if (arr == null || arr.length == 0) {
throw new IllegalArgumentException("arr can not be empty");
}
// 将数组的第一个元素设置为链表的第一个节点
this.val = arr[0];
ListNode cur = this;
for (int i = 1; i < arr.length; i++) {
cur.next = new ListNode(arr[i]);
cur = cur.next;
}
}
/**
* 以当前节点为头节点的链表信息字符串
*
* @return string
*/
public String toString() {
StringBuilder res = new StringBuilder();
ListNode cur = this;
while (cur != null) {
res.append(cur.val).append("->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}删除链表中的元素，代码实现
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
122package demo.recursion;
/**
* leetcode203题：删除连中的元素
* 删除链表中等于给定值val的所有元素
*
* @author jingLv
* @date 2020/12/14
*/
public class RemoveLinkedNode {
/**
* 删除链表中等于给定值val的所有元素
*
* @param head 链表头节点
* @param val 删除的值
* @return 链表节点
*/
public ListNode removeElements(ListNode head, int val) {
// 头节点不为空，且头节点的值等于给定的值（头节点就是需要删除的值），特殊处理
while (head != null && head.val == val) {
// 删除节点的过程
ListNode delNode = head;
head = head.next;
delNode.next = null;
}
// 如果头节点为空，则链表为空，直接返回null
if (head == null) {
return null;
}
// 需要删除的元素在链表中间
// 从头节点开始遍历，找到需要删除的节点
ListNode prev = head;
while (prev.next != null) {
if (prev.next.val == val) {
// 找到删除的节点
ListNode delNode = prev.next;
// 将当前的节点下一个节点指向删除元素指向的下一个节点
prev.next = delNode.next;
// 将删除的节点置为空
delNode.next = null;
} else {
prev = prev.next;
}
}
return head;
}
/**
* 删除链表中等于给定值val的所有元素--优化版
*
* @param head 头节点
* @param val 删除的节点
* @return 链表节点
*/
public ListNode removeE(ListNode head, int val) {
while (head != null && head.val == val) {
head = head.next;
}
if (head == null) {
return null;
}
ListNode prev = head;
while (prev.next != null) {
if (prev.next.val == val) {
prev.next = prev.next.next;
} else {
prev = prev.next;
}
}
return head;
}
/**
* 删除链表中等于给定值val的所有元素--使虚拟头节点
*
* @param head 头节点
* @param val 删除的节点的值
* @return 链表节点
*/
public ListNode removeElementsDummy(ListNode head, int val) {
// 设置虚拟头节点
ListNode dummyHead = new ListNode(-1);
// 虚拟头节点下一个节点是头节点
dummyHead.next = head;
// 从头节点开始遍历，找到需要删除的节点
ListNode prev = dummyHead;
while (prev.next != null) {
if (prev.next.val == val) {
prev.next = prev.next.next;
} else {
prev = prev.next;
}
}
return dummyHead.next;
}
/**
* 删除链表中等于给定值val的所有元素--使用递归解决问题
*
* @param head 头节点
* @param val 删除的节点的值
* @return 链表节点
*/
public ListNode removeElementsRecursion(ListNode head, int val) {
// 如果头节点为空，则链表为空
if (head == null) {
return null;
}
// 头节点，后面跟着的链表
// ListNode result = removeElementsRecursion(head.next, val);
// if (head.val == val) {
// return result;
// } else {
// head.next = result;
// }
// return head;
// 头节点，后面跟着的链表
head.next = removeElementsRecursion(head.next, val);
return head.val == val ? head.next : head;
}
}测试代码
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
29public static void main(String[] args) {
System.out.println("---------------removeElements---------------");
int[] nums1 = {1, 2, 6, 3, 4, 5, 6};
ListNode head1 = new ListNode(nums1);
System.out.println("未删除元素的链表：" + head1);
ListNode result1 = (new RemoveLinkedNode()).removeElements(head1, 6);
System.out.println("已删除元素的链表：" + result1 + ",removeElements");
System.out.println("---------------removeE---------------");
int[] nums2 = {1, 2, 6, 3, 4, 5, 6};
ListNode head2 = new ListNode(nums2);
System.out.println("未删除元素的链表：" + head2);
ListNode result2 = (new RemoveLinkedNode()).removeE(head2, 6);
System.out.println("已删除元素的链表：" + result2 + ",removeE");
System.out.println("---------------removeElementsDummy---------------");
int[] nums3 = {1, 2, 6, 3, 4, 5, 6};
ListNode head3 = new ListNode(nums3);
System.out.println("未删除元素的链表：" + head3);
ListNode result3 = (new RemoveLinkedNode()).removeElementsDummy(head2, 6);
System.out.println("已删除元素的链表：" + result3 + ",removeElementsDummy");
System.out.println("---------------removeElementsRecursion---------------");
int[] nums = {1, 2, 6, 3, 4, 5, 6};
ListNode head = new ListNode(nums);
System.out.println("未删除元素的链表：" + head);
ListNode result = (new RemoveLinkedNode()).removeElementsRecursion(head, 6);
System.out.println("已删除元素的链表：" + result + ",removeElementsRecursion");
}
执行结果
递归运行的机制：递归的微观解读
求和代码解读
- 递归函数的调用，本质就是函数调用
- 只不过调用的函数是自己而已
1 | /** |
为了分析简单，我们使用只有两个元素的数组 arr=[6,10]
第一次调用：sum(arr,0)
使用sun(arr,0)进行调用，进入方法体之后，由于不满足递归的基本条件，进而继续调用sum（arr,1）方法，如下：
第二次调用：sum(arr,1)
使用sun(arr,1)进行调用，进入方法体之后，由于不满足递归的基本条件，进而继续调用sum（arr,2）方法，此时调用过程如下：
当调用sum(arr,2)时，由于此时已经满足了递归的基本条件，结果直接返回0，回到上一次中断的位置，也就是下图中调用sum(arr,1) 方法中的sum（arr,l+1）处，如下图：
代码从中断处继续向下执行，返回arr[1]=10, x=0因此res=10,此时返回值为res=10;
此时代码也将回到sum(arr,1)父亲的调用中，也就是sum(arr,0)中。
代码从中断处继续向下执行，返回arr[0]=6, x=10因此res=16,此时返回值为res=16;
通过递归得到了我们最终的结果为16。
从上述的过程中印证了：递归函数的调用，本质就是函数调用（自身函数）—也就是使用不同的参数，执行相同的逻辑。
递归删除节点代码解读
1 | /** |
为了分析的方便，我们对方法体中的代码做一个简单的标识1,2,3，结果如下图：
分析的简便，我们来进行模拟调用，对6—>7—>8—>null 删除元素为7的节点：
注意：下面的分析中我们使用1,2,3这样的编号（下图红色的圆则是说明的是步骤编号），表示代码执行到的位置
第一次调用：
首先传入头结点为6的链表，由于不满足递归的基本结束条件，再一次触发第二次调用，此时链表变为头结点为7的链表：
第二次调用：
此时链表的头结点变为7，由于不满足递归的基本结束条件，再一次触发第三次调用，此时链表变为头结点为8的链表：
第三次调用：
此时链表的头结点变为8，由于不满足递归的基本结束条件，再一次触发第四次调用，此时链表变为空链表：
第四次调用中，由于此时已经满足了递归的基本条件，回到上一次中断的位置也就是2的位置，返回值为null，如下：
此时的链表为头结点为8的链表，如上图黄色区域，执行第三步代码之后，返回的结果为为头结点为8的链表，即为8–>null，并将该结果返回到上一步调用，也就是标号为2的地方，得到结果为7–>8–>null的链表。
然后继续执行第三步，此时链表7–>8–>null满足删除条件，也就是head.val=val=7,将执行head.next,返回最终结果为8–>null，如下：
回到父级调用的中断位置，得到的结果为6–>8—>null，然后执行第三步代码,判断此时的链表的head.val是否等于val=7,此时的链表不满足，直接返回head，也就是6–8–>null
到此递归调用得以结束，完成过程如下：
递归的调用是由代价的：函数调用（时间开销）+系统栈空间,但是使用递归书写逻辑是更为简单的。
递归算法的调试
打印输出方式，需要在代码中进行拆解，并加入步骤的输出语句
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
59package demo.recursion;
/**
* 打印输出方式 -- 递归算法的调试
*
* @author jinglv
* @date 2021/03/22
*/
public class Solution {
/**
* 递归删除链表节点
*
* @param head 头节点
* @param val 删除的节点
* @param depth 递归调用深度
* @return 已删除节点的链表
*/
public ListNode removeElements(ListNode head, int val, int depth) {
String depthString = generateDepthString(depth);
System.out.print(depthString);
System.out.println("Call: remove " + val + " in " + head);
if (head == null) {
System.out.print(depthString);
System.out.println("Return:" + head);
return null;
}
ListNode res = removeElements(head.next, val, depth + 1);
System.out.print(depthString);
System.out.println("After remove:" + val + ":" + res);
ListNode ret;
if (head.val == val) {
ret = res;
} else {
head.next = res;
ret = head;
}
System.out.print(depthString);
System.out.println("Return:" + ret);
return ret;
}
private String generateDepthString(int depth) {
StringBuilder result = new StringBuilder();
for (int i = 0; i < depth; i++) {
// 每深度调用一次，添加"--"，掉用的越深，则得到的字符串越长
result.append("--");
}
return result.toString();
}
public static void main(String[] args) {
int[] nums = {1, 2, 6, 3, 4, 5, 6};
ListNode head = new ListNode(nums);
System.out.println(head);
ListNode res = (new Solution()).removeElements(head, 6, 0);
System.out.println(res);
}
}执行结果如下：
链表的递归实现
近乎和链表相关的所有操作，都可以使用递归的形式完成，使用递归的方式实现链表的增删改查，代码如下：
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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351package demo.structure.linked;
import javafx.util.Pair;
/**
* 使用递归的方式实现链表
*
* @author jinglv
* @date 2021/03/22
*/
public class LinkedListForRecursion<E> {
private class Node {
/**
* 节点中的元素
*/
public E e;
/**
* 指针
*/
public Node next;
/**
* 构造函数--初始化节点
*
* @param e 元素
* @param next 指针
*/
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
/**
* 构造函数--初始化节点
*
* @param e 元素
*/
public Node(E e) {
this(e, null);
}
/**
* 构造函数--初始化节点
*/
public Node() {
this(null, null);
}
/**
* 元素字符串输出
*
* @return String
*/
public String toString() {
return e.toString();
}
}
/**
* 链表中的头节点
*/
private Node head;
/**
* 链表中元素的个数
*/
private int size;
/**
* 无参构造函数--初始化链表
*/
public LinkedListForRecursion() {
head = null;
size = 0;
}
/**
* 获取链表中元素的个数
*
* @return 元素的个数
*/
public int getSize() {
return size;
}
/**
* 判断链表是否为空
*
* @return boolean
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 链表中添加元素
*
* @param index 位置
* @param e 元素
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed.Illegal index.");
}
head = add(head, index, e);
size++;
}
/**
* 在以node为头节点的链表index位置插入元素e--递归算法
*
* @param node 头节点
* @param index 位置
* @param e 元素
* @return 节点
*/
private Node add(Node node, int index, E e) {
// 如果插入的位置是头节点
if (index == 0) {
return new Node(e, node);
}
node.next = add(node.next, index - 1, e);
return node;
}
/**
* 在链表头添加的元素e
*
* @param e 元素
*/
public void addFirst(E e) {
add(0, e);
}
/**
* 在链表末尾天机新的元素e
*
* @param e 元素
*/
public void addLast(E e) {
add(size, e);
}
/**
* 获取链表的第index(0-based)个位置的元素
*
* @param index 位置
* @return 元素
*/
public E get(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed.Illegal index.");
}
return get(head, index);
}
/**
* 在以node为头节点的链表在，找到第index个元素--递归算法
*
* @param node 头节点
* @param index 位置
* @return 元素
*/
private E get(Node node, int index) {
if (index == 0) {
return node.e;
}
return get(node.next, index - 1);
}
/**
* 获取链表的第一个元素
*
* @return 元素
*/
public E getFirst() {
return get(0);
}
/**
* 获得链表的最后一个元素
*
* @return 元素
*/
public E getLast() {
return get(size - 1);
}
/**
* 修改链表的第index(0-based)个位置的元素为e
*
* @param index 位置
* @param e 元素
*/
public void set(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed.Illegal index.");
}
set(head, index, e);
}
/**
* 修改以node为头节点的链表中，第index(0-based)个位置的元素为e--递归算法
*
* @param node 节点
* @param index 位置
* @param e 元素
*/
private void set(Node node, int index, E e) {
if (index == 0) {
node.e = e;
return;
}
set(node.next, index - 1, e);
}
/**
* 查找链表中是否有元素e
*
* @param e 元素
* @return boolean
*/
public boolean contains(E e) {
return contains(head, e);
}
/**
* 以node为节点的链表中，查找是都存在元素e--递归算法
*
* @param node 节点
* @param e 元素
* @return boolean
*/
private boolean contains(Node node, E e) {
if (node == null) {
return false;
}
if (node.e.equals(e)) {
return true;
}
return contains(node.next, e);
}
/**
* 从链表删除index(0-based)位置元素，返回删除的元素
*
* @param index 位置
* @return 元素
*/
public E remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed.Illegal index.");
}
Pair<Node, E> res = remove(head, index);
size--;
head = res.getKey();
return res.getValue();
}
/**
* 以node为头节点的链表中，删除第index位置的元素--递归算法
* 返回值包含两个元素，删除后的链表头节点和删除的值
*
* @param node 节点
* @param index 位置
* @return 节点元素
*/
private Pair<Node, E> remove(Node node, int index) {
if (index == 0) {
return new Pair<>(node.next, node.e);
}
Pair<Node, E> res = remove(node.next, index - 1);
node.next = res.getKey();
return new Pair<>(node, res.getValue());
}
/**
* 从链表中删除第一个元素，返回删除的元素
*
* @return 元素
*/
public E removeFirst() {
return remove(0);
}
/**
* 从链表中删除最后一个元素，返回删除的元素
*
* @return 元素
*/
public E removeLast() {
return remove(size - 1);
}
/**
* 从链表中删除指定的元素
*
* @param e 元素
*/
public void removeElement(E e) {
head = removeElement(head, e);
}
/**
* 以node为头节点的链表中，删除元素e--递归算法
*
* @param node 节点
* @param e 元素
* @return 节点
*/
private Node removeElement(Node node, E e) {
if (node == null) {
return null;
}
if (node.e.equals(e)) {
size--;
return node.next;
}
node.next = removeElement(node.next, e);
return node;
}
/**
* 格式化输出链表
*
* @return String
*/
public String toString() {
StringBuilder res = new StringBuilder();
Node current = head;
while (current != null) {
res.append(current).append("->");
current = current.next;
}
res.append("NULL");
return res.toString();
}
public static void main(String[] args) {
LinkedListForRecursion<Integer> list = new LinkedListForRecursion<>();
for (int i = 0; i < 10; i++) {
list.addFirst(i);
}
System.out.println(list);
while (!list.isEmpty()) {
System.out.println("removed:" + list.removeLast());
}
}
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Jing's Blog！
