概念
简单地说就是方法自己调用自己，每次调用时传入不同的变量。递归有助于编程者解决复杂的问题，同时让代码变得简洁。
能解决的问题
- 各种数学问题如：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_计科基础/数据结构与算法/应用/汉诺塔%}
