一文详解“递归“在算法中的应用
找往期文章包括但不限于本期文章中不懂的知识点：
个人主页：我要学编程(ಥ_ಥ)-CSDN博客
所属专栏： 递归、搜索与回溯算法专题
目录
递归的介绍
面试题08.06.汉诺塔问题
21.合并两个有序链表
206.反转链表
24.两两交换链表中的节点
50. Pow(x, n)
递归的介绍
递归就是指函数自己调用自己，这个概念应该算是倒背如流了。那为啥会有递归呢？ 本质上是在解决一个主问题时，发现有一个相同的子问题，同样解决子问题时，还发现有一个相同子问题。这就是自己调用自己。
面对递归时，编写代码需要有三步：
1、找到重复的子问题——递归函数的函数头
2、单独解决子问题——递归函数的函数体
3、递归的结束条件——什么情况下无需递归了
接下来我们通过一些题目来彻底弄懂"递归"。
面试题08.06.汉诺塔问题
题目：
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。
示例1:
输入：A = [2, 1, 0], B = [], C = [] 输出：C = [2, 1, 0]示例2:
输入：A = [1, 0], B = [], C = [] 输出：C = [1, 0]提示:
- A中盘子的数目不大于14个。
思路：
根据上面的图，我们可以知道当有 n个盘子时，先将n-1个盘子借助C移动到B，再将第n个盘子移动到C，最后将B的n-1个盘子借助A移动到C。
代码实现：
class Solution {
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
han(A, A.size(), B, C);
}
private void han(List<Integer> A, int n, List<Integer> B, List<Integer> C) {
if (n == 1) {
// 直接把A中的盘子给C
C.add(A.remove(A.size()-1));
return;
}
// 1、先将n-1个盘子，从A借助C移动到B
han(A, n-1, C, B);
// 2、将A中最后一个盘子移动到C
C.add(A.remove(A.size()-1));
// 3、最后将B中的n-1个盘子借助A移动到C
han(B, n-1, A, C);
}
}注意：如果是在笔试上遇到了，可以采取下面这种不讲武德的写法：
class Solution {
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
for (Integer i : A) {
C.add(i);
}
}
}21.合并两个有序链表
题目：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]示例 2：
输入：l1 = [], l2 = [] 输出：[]示例 3：
输入：l1 = [], l2 = [0] 输出：[0]提示：
- 两个链表的节点数目范围是
[0, 50]-100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
思路：
定义一个函数，其功能为将链表1 与 链表进行有序合并，并返回合并后的头节点。
代码实现：
class Solution {
// 合并两个有序链表并返回头节点
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 1、函数的截止条件
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
// 2、找到值小的结点作为头
if (list1.val <= list2.val) {
// 以list1作为头，合并剩下的链表
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
// 以list2作为头，合并剩下的链表
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}206.反转链表
题目：
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]示例 2：
输入：head = [1,2] 输出：[2,1]示例 3：
输入：head = [] 输出：[]提示：
- 链表中节点的数目范围是
[0, 5000]-5000 <= Node.val <= 5000
思路：
1、宏观看待：
2、看成单分支的树：
代码实现：
class Solution {
// 把head链表逆置，并返回新的头节点
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 将head后面的结点翻转，并返回新的结点
ListNode newHead = reverseList(head.next);
// 将当前结点的下一个结点的next指针指向当前结点
head.next.next = head;
// 并把当前结点的next指针置为null
head.next = null;
return newHead;
}
}24.两两交换链表中的节点
题目：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]示例 2：
输入：head = [] 输出：[]示例 3：
输入：head = [1] 输出：[1]提示：
- 链表中节点的数目在范围
[0, 100]内0 <= Node.val <= 100
思路：
代码实现：
迭代版：
class Solution {
// 不讲武德的解法：直接交换结点的值
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode prev = head, cur = head.next;
while (cur != null) { // cur是要交换的结点
int tmp = prev.val;
prev.val = cur.val;
cur.val = tmp;
prev = prev.next.next;
cur = cur.next == null ? null : cur.next.next;
}
return head;
}
// 中规中矩的写法
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = new ListNode(-1, head); // 哨兵位节点
// 修改cur后面的两个结点
ListNode node1 = head, node2 = head.next, cur = newHead;
while (node2 != null) { // node2为null时，均满足上述两种情况
// 下面的修改不能变换
node1.next = node2.next;
node2.next = node1;
cur.next = node2;
// 修改指针指向
cur = node1;
node1 = cur.next;
node2 = node1 == null ? null : node1.next;
}
return newHead.next;
}
}递归版：
class Solution {
// 递归的写法
// 赋予swapPairs函数一个功能：给你一个指针，将这个指针所指向的链表节点两两交换
public ListNode swapPairs(ListNode head) {
// 1、递归的截止条件
if (head == null || head.next == null) {
return head;
}
// 先帮我把后面的结点（除前面两个结点之外）全部两两交换
ListNode cur = swapPairs(head.next.next);
// 3、解决一个子问题：交换两个结点，并返回新的头结点
ListNode node = head.next;
head.next = cur;
node.next = head;
return node;
}
}50. Pow(x, n)
题目：
实现 pow(x, n) ，即计算
x的整数n次幂函数（即，x ^ n）。示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000示例 2：
输入：x = 2.10000, n = 3 输出：9.26100示例 3：
输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25提示：
-100.0 < x < 100.0-2^31 <= n <= 2^31-1n是一个整数- 要么
x不为零，要么n > 0。-10^4 <= x^n <= 10^4
思路：暴力枚举的思路应该是非常容易想到的，但数据量过大，很容易就超时了。接下来就是需要去优化，这里需要用到一个知识点："快速幂"。
注意：上述的计算方法是不断去 /2 ，将 x^1 计算出来，然后回溯的过程中，计算出更大的数，但也有缺陷：n只能处理>0的数，而等于0与小于0需要我们额外去处理。这也很好处理：当n=0时，直接返回1即可；当n<0时，直接将x改为 1/x，n改为-n就行了。但又有一个小细节：当n = -2^31时，-n = 2^31，但是这个数超出了整数的范围，最终的结果还是 -2^31，不过由于这里我们不是去直接计算的，而是通过递归来不断缩小 n 的值，因此对最终的结果不影响。但是C++与Java不一样，C++是未定义的行为通常要编译器的优化结果，因此会导致计算错误。如下图所示：
准确来说，C++通常也是按照数字轮的方式来处理的，但是由于编译器的实现不同，可能会导致最终的结果不一样（我本身没有学过C++，不是很懂，问的ChatGPT） 。
代码实现：
class Solution {
// 快速幂+递归
public double myPow(double x, int n) {
// 当n<0时，是无法求出最终结果的
return n < 0 ? pow(1/x, -n) : pow(x, n);
}
// 赋予pow函数的意义：求出x的n次方
private double pow(double x, int n) {
// 1、递归的截止条件
if (n == 1) {
return x;
}
if (n == 0) { // 避免出现n=0的情况
return 1;
}
// 求x的n次方，就先求x的n/2次方
double tmp = pow(x, n/2);
// 求出x的n/2次方后，就可以通过两者相乘的方式求出最终结果
return n % 2 == 0 ? tmp*tmp : tmp*tmp*x;
}
}好啦！本期 一文详解“递归“在算法中的应用 的学习之旅 就到此结束啦！我们下一期再一起学习吧！