目录

递归

概念

简单地说就是方法自己调用自己,每次调用时传入不同的变量。递归有助于编程者解决复杂的问题,同时让代码变得简洁。

能解决的问题

  • 各种数学问题如: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个节点做一次反转。

死扣递归很多时候还是有必要的,它不仅是一种优美的思路,简洁的代码,更体现的是对函数不断调入与回溯这一过程的整体把握,基于整个递归程序流程的理解再去写非递归会更简单。递归的过程其实就是函数不断的调入,在计算机中每一个函数都是一个栈帧,函数的调入与完成对应入栈与出栈。

小结

递归三要素:

  1. 定义递归函数功能
  2. 寻找结束条件
  3. 寻找等价关系

递归的优化

考虑是否重复计算

例如对于案例2那道题,f(n) = f(n-1) + f(n-2)。递归调用的状态图如下:

http://img.cana.space/picStore/20210623222713.png

光是这张图里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_计科基础/数据结构与算法/应用/汉诺塔%}