递归算法详解
- 递归
- 题目一: 汉诺塔 (easy)
- 1. 题⽬链接:
- 2. 题⽬描述:
- 3. 解法(递归):
- 算法思路:
- 算法流程:
- 4.代码
- 题目二:合并两个有序链表(easy)
- 1. 题⽬链接:
- 2. 题⽬描述:
- 3. 解法(递归):
- 4.代码
- 题目三: 反转链表(easy)
- 1. 题⽬链接:
- 2. 题⽬描述:
- 3. 解法(递归):
- 4. 代码
递归
在解决⼀个规模为n的问题时,如果满⾜以下条件,我们可以使⽤递归来解决:
A. 问题可以被划分为规模更⼩的⼦问题,并且这些⼦问题具有与原问题相同的解决⽅法。
B. 当我们知道规模更⼩的⼦问题(规模为 n - 1)的解时,我们可以直接计算出规模为 n 的问题 的解。
C. 存在⼀种简单情况,或者说当问题的规模⾜够⼩时,我们可以直接求解问题。 ⼀般的递归求解过程如下:
a. 验证是否满⾜简单情况。
b. 假设较⼩规模的问题已经解决,解决当前问题。
题目一: 汉诺塔 (easy)
1. 题⽬链接:
https://leetcode.cn/problems/hanota-lcci/description/
2. 题⽬描述:
3. 解法(递归):
算法思路:
这是⼀道递归⽅法的经典题⽬,我们可以先从最简单的情况考虑:
• 假设 n = 1,只有⼀个盘⼦,很简单,直接把它从 A 中拿出来,移到 C 上;
• 如果 n = 2 呢?这时候我们就要借助 B 了,因为⼩盘⼦必须时刻都在⼤盘⼦上⾯,共需要 3 步(为
了⽅便叙述,记 A 中的盘⼦从上到下为 1 号,2 号):
a. 1 号盘⼦放到 B 上;
b. 2 号盘⼦放到 C 上;
c. 1 号盘⼦放到 C 上。
⾄此,C 中的盘⼦从上到下为 1 号, 2 号。
• 如果 n > 2 呢?这是我们需要⽤到 n = 2 时的策略,将 A 上⾯的两个盘⼦挪到 B 上,再将最⼤的盘
⼦挪到 C 上,最后将 B 上的⼩盘⼦挪到 C 上就完成了所有步骤。例如 n = 3 时如下图:
因为 A 中最后处理的是最⼤的盘⼦,所以在移动过程中不存在⼤盘⼦在⼩盘⼦上⾯的情况。
则本题可以被解释为:
1. 对于规模为 n 的问题,我们需要将 A 柱上的 n 个盘⼦移动到C柱上。
2. 规模为 n 的问题可以被拆分为规模为 n-1 的⼦问题:
a. 将 A 柱上的上⾯ n-1 个盘⼦移动到B柱上。
b. 将 A 柱上的最⼤盘⼦移动到 C 柱上,然后将 B 柱上的 n-1 个盘⼦移动到C柱上。
3. 当问题的规模变为 n=1 时,即只有⼀个盘⼦时,我们可以直接将其从 A 柱移动到 C 柱。
• 需要注意的是,步骤 2.b 考虑的是总体问题中的 ⼦问题b 情况。在处理⼦问题的 ⼦问题b 时,我们 应该将 A
柱中的最上⾯的盘⼦移动到 C 柱,然后再将 B 柱上的盘⼦移动到 C 柱。在处理总体问题 的 ⼦问题b 时,A
柱中的最⼤盘⼦仍然是最上⾯的盘⼦,因此这种做法是通⽤的。
算法流程:
递归函数设计:
函数头的设计(重复子问题)
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C)
-
返回值:⽆;
-
参数:三个柱⼦上的盘⼦,当前需要处理的盘⼦个数(当前问题规模)。
函数体的
函数体的设计(关注一个具体的子问题在做什么) -
函数作⽤:将 A 中的上⾯ n 个盘⼦挪到 C 中。
递归函数流程:
-
当前问题规模为 n=1 时,直接将 A 中的最上⾯盘⼦挪到 C 中并返回;
-
递归将 A 中最上⾯的 n-1 个盘⼦挪到 B 中;
-
将 A 中最上⾯的⼀个盘⼦挪到 C 中;
-
将 B 中上⾯ n-1 个盘⼦挪到 C 中。
4.代码
class Solution
{public void hanota(List<Integer> a, List<Integer> b, List<Integer> c) {dfs(a, b, c, a.size());}public void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n){if(n == 1){c.add(a.remove(a.size() - 1));return;}dfs(a, c, b, n - 1);c.add(a.remove(a.size() - 1));dfs(b, a, c, n - 1);}}
题目二:合并两个有序链表(easy)
1. 题⽬链接:
https://leetcode.cn/problems/merge-two-sorted-lists/description/
2. 题⽬描述:
3. 解法(递归):
算法思路:
A. 递归函数的含义:交给你两个链表的头结点,你帮我把它们合并起来,并且返回合并后的头结点;
B. 函数体:选择两个头结点中较⼩的结点作为最终合并后的头结点,然后将剩下的链表交给递归函数 去处理;
C. 递归出⼝:当某⼀个链表为空的时候,返回另外⼀个链表。
4.代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/class Solution
{public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1 == null) return l2;if(l2 == null) return l1;if(l1.val <= l2.val){l1.next = mergeTwoLists(l1.next, l2);return l1;}else{l2.next = mergeTwoLists(l1, l2.next);return l2;}}}
题目三: 反转链表(easy)
1. 题⽬链接:
https://leetcode.cn/problems/reverse-linked-list/description/
2. 题⽬描述:
3. 解法(递归):
算法思路:
递归函数的含义:交给你⼀个链表的头指针,你帮我逆序之后,返回逆序后的头结点;
函数体:先把当前结点之后的链表逆序,逆序完之后,把当前结点添加到逆序后的链表后⾯即可;
递归出⼝:当前结点为空或者当前只有⼀个结点的时候,不⽤逆序,直接返回。
4. 代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/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;}
}