递归算法专题——真正理解递归和正确使用递归力扣实战应用
目录
1、使用递归
1.1 如何理解递归
1.2 如何写好一个递归算法
2、 算法应用【leetcode】
2.1 题一：汉诺塔问题【面试题】
2.1.1 算法原理
2.1.2 算法代码
2.2 题二：合并两个有序链表
2.2.1 算法原理
2.2.2 算法代码
2.3 题三：反转链表
2.3.1 算法原理
2.3.2 算法代码
2.4 题四：两两交换链表中的节点
2.4.1 算法原理
2.4.2 算法代码
2.5 题五：Pow(x，n)
2.5.1 算法原理
2.5.2 算法代码
1、使用递归
1.1 如何理解递归
大家都知道，递归其实就是自己调用自己。
但是，为什么要使用递归呢？换句话说，为什么要自己调用自己呢？我们应该在什么情况下使用递归呢？又如何才能写好一个递归呢？
为什么使用递归，其实就是一个主问题中包含了相同问题的子问题，而子问题又包含了相同问题的子问题，即：出现了重复的子问题，进而我们只需要将焦点放在这个重复的子问题上，使用一个相同的方案来解决整个主问题，这就是使用递归的原因。
在理解递归后，要想得心应手的使用递归算法解题，我们必须以宏观的角度看待递归：
- 不要在意递归的细节展开图(因为我们知道，展开图一定是正确的)
- 将递归函数当成一个黑盒
- 无条件相信这个黑盒一定能完成任务，一定能给我们带来想要的结果
1.2 如何写好一个递归算法
一个递归中，有三个要素是必不可少的：1.函数头 2.函数体 3.函数出口(回退条件)
所以要想写好递归算法，那必须清楚的知道这三个要素该如何正确设计与书写：
- 找到重复的子问题 --> 函数头的设计
- 只关心其中一个子问题是如何解决的 --> 函数体的书写
- 注意递归函数的出口
虽然以上均为口头理论知识，但却尤为重要，当我们能够以宏观角度看待递归时，那递归的书写和使用将会非常得心应手。
2、 算法应用【leetcode】
2.1 题一：汉诺塔问题【面试题】
. - 力扣（LeetCode）
2.1.1 算法原理
通过画图可以发现，移动盘子的过程其实就是一个重复的子问题，因此我们使用递归求解。
【注意：一定要以宏观角度看待递归，相信这个递归函数一定能够完成任务，不要在意细节展开图，否则做题会很费劲】
- 1.重复子问题 -> 函数头
将x柱子上的一些盘子，借助y柱子，转移到z柱子上: dfs(x,y,z, n);
- 2.只关注重复子问题中的其中一个子问题 -> 函数体
①现将x柱子上的n-1个盘子借助c盘转移到y柱子上，②再将x柱子上最后一个盘子转移到z柱子上，③最后再将y柱子上的n-1个盘子借助x柱子转移到z柱子上：①dfs(x, z, y, n-1); ②x.back()-> z;③dfs(y,x,z,n-1);
- 3.函数出口
n==1时，x.back() 转移到z柱子上；
2.1.2 算法代码
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);
}
}2.2 题二：合并两个有序链表
. - 力扣（LeetCode）
2.2.1 算法原理
为什么可以使用递归？选出值最小的节点，接着合并剩下的链表和另外一个链表；再选出值次小的节点，接着合并剩下的链表和另外一个链表；......依然是重复的子问题，可以递归求解。
同样，站在宏观角度看待递归。
- 先选出值最小节点，接着让这个递归函数合并剩下的链表并返回合并后的头结点，(我不管它怎么做到的，相信它一定可以做到)
- 接着，将最小的节点和返回后的(合并好的)链表相连接
- 返回头结点
- 函数出口：当为节点不存在时(node == null)，说明不需要合并，为函数出口，递归回退
2.2.2 算法代码
/**
* 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 list1, ListNode list2) {
if(list1 == null) return list2;
if(list2 == null) return list1;
if(list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
}else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}2.3 题三：反转链表
. - 力扣（LeetCode）
2.3.1 算法原理
- 让递归函数反转链表(宏观角度，相信它一定可以完成)
- 并且递归函数返回反转链表后的头结点
- 修改当前节点与反转后链表的指向
2.3.2 算法代码
/**
* 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;
}
}2.4 题四：两两交换链表中的节点
. - 力扣（LeetCode）
2.4.1 算法原理
- 宏观角度，先把前两个节点看做整体
- 使用递归函数两两交换这两个节点后的节点，并返回交换后链表的头结点
- 再反转前两个节点并且修改链表的指向关系
- 当节点为空或者只有一个节点时，为函数出口
2.4.2 算法代码
/**
* 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 swapPairs(ListNode head) {
if(head == null || head.next == null) return head;
ListNode tmp = swapPairs(head.next.next);
ListNode newHead = head.next;
newHead.next = head;
head.next = tmp;
return newHead;
}
}2.5 题五：Pow(x，n)
. - 力扣（LeetCode）
2.5.1 算法原理
这里再次强调一下：一定要以宏观的角度看待递归！！！把递归函数当做一个黑盒，相信这个黑盒一定能够完成相关任务！
一个数的n次方，就是这个数的n/2次方* 这个数的n/2次方；
一个数的n/2次方，就是这个数的n/4次方* 这个数的n/4次方；
一个数的n/4次方，就是这个数的n/8次方* 这个数的n/8次方；
.........
一个数的0次方，就是1；
综上所示，出现了重复的子问题，我们可以使用递归算法解题。
- 站在宏观角度，要得到当前数的n次方，就要得到其n/2次方(tmp)，而tmp*tmp就是当前数的n次方
- 而递归函数就要为我们返回数的n/2次方(tmp)，我们要无条件相信它。tmp = pow(x, n/2)；
- 在n==1的函数当中，要得到0次方(n/2=0)时的数值，任何数的0次方为1，此时为函数出口，返回1
- 当n/2不能整除时，返回tmp*tmp*x即可
- 注意n为负数的情况，当成正数计算，最终返回其倒数即可
2.5.2 算法代码
class Solution {
public double myPow(double x, int n) {
return n < 0 ? 1 / pow(x, -n) : pow(x, n);
}
public double pow(double x, int n) {
if(n == 0) return 1;
//宏观角度看待递归，得到当前数n/2幂的值
double tmp = pow(x, n / 2);
return (n % 2 == 0) ? tmp * tmp : tmp * tmp * x;
}
}END