概念
简单地说就是方法自己调用自己,每次调用时传入不同的变量。递归有助于编程者解决复杂的问题,同时让代码变得简洁。
能解决的问题
- 各种数学问题如:8皇后问题,汉诺塔,阶乘,迷宫
- 很多算法中也有用到递归,如快排,归并排序、二分查找、分值算法等
- 栈解决的问题也可以使用递归解决
使用规则
- 执行一个方法时,就创建一个新的空间(栈帧)
- 方法的局部变量是独立的
- 递归必须向退出递归的条件逼近,否则就是无限递归,最终StackOverflowError
- 当一个方法执行完毕就会返回,遵守谁调用返回给谁。
递归三要素
我们以反转链表为例,将链表1->2->3->4反转
要素一:明确这个函数要干什么
这个函数要干什么完全取决于你的定义,也就是说,我们先不管函数里面的代码是什么,而是要先明白这个函数是用来干什么的
例如,我们定义这样一个函数
1
2
3
4
|
// 对给定链表进行反转
ListNode reverse(ListNode node) {
}
|
我们已经定义好了函数的功能,接下来我们看第二要素
要素二:寻找递归结束的条件
所谓递归就是在函数内部会调用函数本身,所以我们必须要找出递归结束的条件,否则会进入死循环。也就是说,我们需要找出参数为啥时,递归才结束,之后把结果返回。请注意,这个时候我们必须能根据这个参数的值,直接知道函数的结果是什么。
例如,上面这个例子,当链表只有一个节点或者是空的话,结果就是自己,如下:
1
2
3
4
5
|
ListNode reverse(ListNode node) {
if(node == null || node.next == null) {
return node;
}
}
|
要素三:找出函数的等价关系式
我们需要不断缩小参数的范围,向边界结束条件逼近。我们可以通过一些辅助的变量或者操作,使原函数结果不变。例如n的阶乘中f(n)=n*f(n-1)。这样范围就由n变成了n-1了。回到反转链表例子中,我们可以先对head.next做反转,有如下:
1
|
ListNode temp = reverse(head.next);
|
我们已经定义了 reverseLis t函数的功能可以把一个单链表反转,所以2->3->4变成了4->3->2,不过1这个节点我们没有碰他,所以1仍指向2, 所以此时链表1->2->3->4 变成了1->2<-3<-4 其中temp指向4
接下来就简单了,将节点2的next指针指向1,1的next指针指向空,也就是等价关系就是 reverse(node) 等价于 reverse(node.next) + 改变下第一个和第二个节点的指向即可, 完整代码如下:
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
|
class Solution {
// 递归函数功能:将链表head反转
public ListNode reverse(ListNode head) {
// 递归结束条件
if(head == null || head.next == null) return head;
// 递归关系式
ListNode temp = reverse(head.next);
// 此时 2->3->4变成了4->3->2,不过1这个节点我们没有碰它,
// 所以1仍指向2, 所以此时链表1->2->3->4 变成了1->2<-3<-4 其中temp指向4
// 我们将2指向1,1指向空
head.next.next = head;
head.next = null;
// 将调整之后的链表返回
return temp;
}
static class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public static void show(ListNode head) {
while(head != null) {
System.out.println(head.val);
head = head.next;
}
}
public static void main(String[] args) {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
n1.next = n2;
n2.next = n3;
n3.next = n4;
show(n1);
System.out.println("======");
Solution solution = new Solution();
ListNode res = solution.reverse(n1);
show(res);
}
}
|
再来个例子,单链表每k个节点逆序,最后不足k个节点保持原样
递归函数功能:
1
2
3
4
|
// 对单链表的每k个节点进行连续,最后不足k个节点保持原样
public ListNode reverseKNodes(ListNode head, int k) {
}
|
递归结束条件:
1
2
3
4
5
6
7
8
9
10
|
public ListNode reverseKNodes(ListNode head, int k) {
// 递归结束条件,当尾部不足k个节点则保持原样
ListNode kTailNode = head;;
// 先定位到k个一组的尾部节点(遍历k-1次),如果是空说明已经到达尾部,且不满足k个节点,保持原样
for(int i = 1; i < k && kTailNode != null; i++) {
kTailNode = kTailNode.next;
}
if(kTailNode == null) {
return head;
}
|
递归等价关系式:
reverseKNodes(ListNode head, int k) 等价于先逆序前k个节点,再拼接剩余节点构成链表的分组逆序结果,完整代码如下:
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
|
package test;
class Solution {
// 1->2->3->4->5->6->7->8
// 对单链表的每k个节点进行连续,最后不足k个节点保持原样
public ListNode reverseKGroup(ListNode head, int k) {
// 递归结束条件,当尾部不足k个节点则保持原样
ListNode kTailNode = head;;
// 先定位到k个一组的尾部节点(遍历k-1次),如果是空说明已经到达尾部,且不满足k个节点,保持原样
for(int i = 1; i < k && kTailNode != null; i++) {
kTailNode = kTailNode.next;
}
if(kTailNode == null) {
return head;
}
// 将单链表分成两组,前k个节点和剩余节点
ListNode nextGroup = kTailNode.next;
kTailNode.next = null;
// 将前k个节点逆序,再拼接后面剩余节点的逆序结果
ListNode newHead = reverse(head);
// 将剩余链表继续分组逆序
ListNode newKHead = reverseKGroup(nextGroup, k);
// 拼接两部分结果,原head已经变成前k个节点的尾节点了
head.next = newKHead;
// 将拼接好的链表返回
return newHead;
}
// 对单链表连续 1->2->3->4
private ListNode reverse(ListNode head) {
if(head == null || head.next == null) {
return head;
}
// 1->2<-3<-4
ListNode temp = reverse(head.next);
// 将2指向1,1指向null
head.next.next = head;
head.next = null;
return temp;
}
static class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public static void show(ListNode head) {
while(head != null) {
System.out.println(head.val);
head = head.next;
}
}
public static void main(String[] args) {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
ListNode n6 = new ListNode(6);
ListNode n7 = new ListNode(7);
ListNode n8 = new ListNode(8);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n7;
n7.next = n8;
show(n1);
System.out.println("======");
Solution solution = new Solution();
ListNode res = solution.reverseKGroup(n1, 3);
show(res);
}
}
|
再来看一道上面这个题目的变形题:
给定一个单链表的头节点 head,实现一个调整单链表的函数,使得每K个节点之间为一组进行逆序,并且从链表的尾部开始组起,头部剩余节点数量不够一组的不需要逆序。(不能使用队列或者栈作为辅助)
例如: 链表:1->2->3->4->5->6->7->8->null, K = 3。那么 6->7->8,3->4->5,1->2各位一组。调整后:1->2->5->4->3->8->7->6->null。其中 1,2不调整,因为不够一组。
其实跟上面这道理类似,只不过我们要先做一层转换,将单链表逆序,按照上题解题过程实现一遍即可,再对结果逆序就可以了
代码如下:
1
2
3
4
5
6
7
8
9
|
public ListNode solve(ListNode head, int k) {
// 调用逆序函数
head = reverse(head);
// 调用每 k 个为一组的逆序函数(从头部开始组起)
head = reverseKGroup(head, k);
// 在逆序一次
head = reverse(head);
return head;
}
|
本题只是说明递归怎么写,当然有更好的做法,一次遍历得到链表长度,对k取余数表示前k个节点不用反转,后面每k个节点做一次反转。
死扣递归很多时候还是有必要的,它不仅是一种优美的思路,简洁的代码,更体现的是对函数不断调入与回溯这一过程的整体把握,基于整个递归程序流程的理解再去写非递归会更简单。递归的过程其实就是函数不断的调入,在计算机中每一个函数都是一个栈帧,函数的调入与完成对应入栈与出栈。
小结
递归三要素:
- 定义递归函数功能
- 寻找结束条件
- 寻找等价关系
递归的优化
考虑是否重复计算
例如对于案例2那道题,f(n) = f(n-1) + f(n-2)。递归调用的状态图如下:

光是这张图里f(5)就重复计算了3次,f(4)4次,这是非常恐怖的,n 越大,重复计算的就越多,所以我们必须进行优化。
可以使用记忆化递归,就是将计算的结果f(4)保存起来,当再次要计算f(4)的时候,如果之前计算过直接使用,否则递归计算
用什么保存呢?可以用数组或者 HashMap 保存,我们用数组来保存把,把 n 作为我们的数组下标,f(n) 作为值,例如 arr[n] = f(n)。f(n) 还没有计算过的时候,我们让 arr[n] 等于一个特殊值,例如 arr[n] = -1。
当我们要判断的时候,如果 arr[n] = -1,则证明 f(n) 没有计算过,否则, f(n) 就已经计算过了,且 f(n) = arr[n]。直接把值取出来就行了。代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
// 我们实现假定 arr 数组已经初始化好的了。
int f(int n){
if(n <= 1){
return n;
}
//先判断有没计算过
if(arr[n] != -1){
//计算过,直接返回
return arr[n];
}else{
// 没有计算过,递归计算,并且把结果保存到 arr数组里
arr[n] = f(n-1) + f(n-1);
reutrn arr[n];
}
}
|
也就是说,使用递归的时候,必要
须要考虑有没有重复计算,如果重复计算了,一定要把计算过的状态保存起来。
考虑是否可以自底向上
对于递归的问题,我们一般都是从上往下递归的,直到递归到最底,再一层一层着把值返回。
不过,有时候当 n 比较大的时候,例如当 n = 10000 时,那么必须要往下递归10000层直到 n <=1 才将结果慢慢返回,如果n太大的话,可能栈空间会不够用。
对于这种情况,其实我们是可以考虑自底向上的做法的。例如我知道
f(1) = 1;
f(2) = 2;
那么我们就可以推出 f(3) = f(2) + f(1) = 3。从而可以推出f(4),f(5)等直到f(n)。因此,我们可以考虑使用自底向上的方法来取代递归,代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public int f(int n) {
if(n <= 2)
return n;
int f1 = 1;
int f2 = 2;
int sum = 0;
for (int i = 3; i <= n; i++) {
sum = f1 + f2;
f1 = f2;
f2 = sum;
}
return sum;
}
|
这种方法,其实也被称之为递推。
使用递归的经典案例——汉诺塔
{%post_link 工作/100_计科基础/数据结构与算法/应用/汉诺塔%}