算法【Java】—— 递归
递归思路
首先我们要分析主问题,如果主问题可以拆分成一个又一个小问题的时候,并且这些小问题的解决方案也是一样的话,我们可以使用递归来解决。
递归函数头的设计是根据子问题的解决需要而设计的
函数体部分则是由如何解决子问题组成
最后就是递归的出口,其实就是分到不能再分的情况。
这里我们不要进行递归展开图的绘制,要相信我们的函数可以完成任务,就像相信你的编译器能进行代码的编译。
下面我们来实战演示一下:
实战演练
汉诺塔
https://leetcode.cn/problems/hanota-lcci/description/
太经典的题目了,这里就直接分析了,不解析题意了。
我们抽象一下,假设我们有 N 个盘子,我们需要先将 N - 1 个盘子借助 C 柱子 移动到 B 柱上,然后将 A 柱 上 的最后一个盘子直接移动到 C 柱上,最后我们将 B 柱 上的 N - 1 个盘子借助 A 柱 移动到 C 柱上
那么我们的递归函数头的设计应该是盘子数量 , 三个柱子(初始位置,助力位置,目标位置)
递归的出口就是不能继续划分的情况也就是只有一个盘子的情况。
class Solution {
public void move(List<Integer> A, List<Integer> B, List<Integer> C, int n) {
if(n == 1) {
C.add(A.remove(A.size() - 1));
return;
}
move(A, C, B, n - 1);
C.add(A.remove(A.size() - 1));
move(B, A, C, n - 1);
}
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
int n = A.size();
move(A, B, C, n);
}
}
合并两个链表
https://leetcode.cn/problems/merge-two-sorted-lists/description/
这道题我们可以采用递归的思路来写,首先找到子问题:
当我们遇到两条链表的时候,我们会选取其中一个 value 值较小的作为新链表的下一个连接结点,你会发现,每次遇到两条非空链表,都是重复上面的操作,所以函数头的参数也就是两条链表。
接着就是函数体的书写,首先需要比较,然后我们思考这个函数是做什么的?很显然,这个函数需要返回一个结点,这个结点需要连接到上一个递归函数的结点后面,所以这个函数应该是返回两个链表的合适的结点。
递归的出口,当其中一条链表为空的时候,返回另一条链表即可。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null) return list2;
if(list2 == null) return list1;
ListNode min = list1.val < list2.val ? list1 : list2;
if(min == list1)
min.next = mergeTwoLists(list1.next, list2);
else
min.next = mergeTwoLists(list1, list2.next);
return min;
}
}
反转链表
https://leetcode.cn/problems/reverse-linked-list/description/
递归的函数的作用:反转链表,返回新的头节点
函数头的设计:需要一个链表参数
函数体设计:当我们使用递归函数会得到类似下图的链表:
当我们得到新的头节点时,我们需要将head.next 这个结点的 next 区域的指向修改为 head, 然后我们还需要将 head 的 next 域修改为 null,为什么需要这个操作,因为最后一个结点的时候,例如上面的 1 号结点,它的next 域指向为空,为了操作的统一,所以这里统一处理为 head.next = null
递归的出口,当 head 为空或者 head 后面没有结点,这时候无需反转链表,直接返回即可。
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
两两交换链表中的节点
https://leetcode.cn/problems/swap-nodes-in-pairs/description/
函数作用:返回一个交换过的链表的头节点,函数头需要一个参数也就是链表的头节点
函数体的设计:
head.next = 递归函数返回的头节点
r2.next = head
递归的出口:当头节点为空,或者头节点后面没有节点的时候,直接返回头节点即可
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode r2 = head.next;
head.next = swapPairs(r2.next);
r2.next = head;
return r2;
}
}
快速幂
https://leetcode.cn/problems/powx-n/
快速幂的方法:假设求 100 的 10 次方:
先求出一半的次方的幂,然后进行自我相乘,如果次方为奇数,则需要再乘 一个 x
那么这个递归函数的作用就是来求出快速幂的,传参有两个, x 和 n
在进行递归之前,我们先处理一下如果次方是负数的情况,需要进行转换,由于负数最小为 2 ^ -31 ,所以转化成(int 类型)的正数的时候,会发生溢出,这里就整型提升一下。
递归的出口:n == 0 ,返回1 ,n == 1 返回 自身。
class Solution {
public double myPow(double x, int n) {
return n < 0 ? 1 / pow(x, -(long)n) : pow(x, n);
}
double pow(double x, long n) {
if(n == 0) return 1;
if(n == 1) return x;
double y = pow(x, n / 2);
return n % 2 == 0 ? y * y : y * y * x;
}
}
递归与循环,搜索,回溯,剪枝的关系
递归和循环都是在重复做一件事情,所以递归和循环是可以相互转换的,当然有时候题目使用递归会好写代码,而有些题目使用循环会好写,这是因为我们递归如果是单分支的树,使用循环会更好,但是如果递归是二叉甚至 N 叉树的时候,使用循环就需要借助栈,,这时候循环就很难写了。
我们来看一下搜索,搜索分为广度优先遍历和深度优先遍历,学过图的老铁们应该很清楚,而我们的递归则是和深度优先遍历一样(简称深搜),所以搜索本质上也是递归,没有很神秘。
回溯,这个大家应该有听过回溯算法,实际还是和递归 / 搜索一样,回溯在递归里的表现就是递归到了底,然后向上回去,回去就是回溯。
剪枝可以说是递归 / 搜索 / 回溯的一个优化,就是你发现有些递归是不需要做的,就不进去递归,简单来看就是一个树有很多的岔路,当你知道有一条岔路绝对不可能是答案的时候,这时候使用剪枝就可以去掉这些没有的树枝,在代码理解来看就是不去这个递归。
在后续的算法文章中我会进行对上面的知识进行题目的代码演示与讲解,这里先抛出这些概念。