算法沉淀——递归（leetcode真题剖析）

递归是一种通过调用自身的方式来解决问题的算法。在递归算法中，问题被分解为更小的相似子问题，然后通过对这些子问题的解进行组合来解决原始问题。递归算法通常包含两个主要部分：

1. 基本情况（Base Case）： 定义问题的最小规模，直接解答而不再进行递归。基本情况是递归算法的出口，防止算法陷入无限递归。
2. 递归步骤： 在问题规模较大时，将问题划分为相似但规模较小的子问题，并通过递归调用解决这些子问题。递归调用自身是递归算法的核心。

递归算法在解决许多问题上非常强大，尤其是对于那些可以通过分解为子问题并且存在重叠子问题的情况。递归通常使算法更加简洁、清晰，但需要谨慎处理基本情况，以避免无限递归。

经典的递归问题包括汉诺塔问题、阶乘计算、斐波那契数列等。递归也在许多算法和数据结构中发挥着重要的作用，例如树的遍历、图的深度优先搜索等。

如何理解递归？

1.递归展开的细节图
2.二叉树中的题目
3.宏观看待递归的过程

1.不要在意递归的细节展开图
2.把递归的函数当成一个黑盒
3.相信这个黑盒一定能完成这个任务

如何写好递归？

1.先找到相同的子问题!!!->函数头的设计
2.只关心某一个子问题是如何解决的 ->函数体的书写
3.注意一下递归函数的出口即可

01.汉诺塔问题

题目链接：https://leetcode.cn/problems/hanota-lcci/

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

示例1:

 输入：A = [2, 1, 0], B = [], C = []
 输出：C = [2, 1, 0]
1
2

示例2:

 输入：A = [1, 0], B = [], C = []
 输出：C = [1, 0]
1
2

提示:

1. A中盘子的数目不大于14个。

思路

对于这类问题我们可以使用数学中的归结思想，先画图分析由1到n的情况，我们可以总结出下面这三个步骤

代码

class Solution {
    void dfs(vector<int>& A, vector<int>& B, vector<int>& C,int n)
    {
        if(n==1){
            C.push_back(A.back());
            A.pop_back();
            return;
        }

        dfs(A,C,B,n-1);
        C.push_back(A.back());
        A.pop_back();
        dfs(B,A,C,n-1);

    }
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        dfs(A,B,C,A.size());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1. 定义一个私有的递归函数 dfs，该函数将 A 柱上的 n 个盘子通过 B 柱移动到 C 柱。参数 A、B 和 C 分别表示三个柱子的盘子状态，n 表示要移动的盘子数量。
2. 在递归函数中，当只有一个盘子时，直接将 A 柱的盘子移到 C 柱上，然后返回。
3. 在递归函数中，先将 A 柱上的 n-1 个盘子通过 C 柱移动到 B 柱上，然后将 A 柱上的最后一个盘子移动到 C 柱上，最后将 B 柱上的 n-1 个盘子通过 A 柱移动到 C 柱上。
4. 在公有函数 hanota 中，调用递归函数 dfs，传入 A、B、C 三个柱子的状态和盘子数量。

02.合并两个有序链表

题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
1
2

示例 2：

输入：l1 = [], l2 = []
输出：[]
1
2

示例 3：

输入：l1 = [], l2 = [0]
输出：[0] 
1
2

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

思路

这里我们如果划分为子问题，每次就拿出最小的那个节点当做头节点，拼接剩下的当前节点尾部的节点和另一个链表的头节点相比较的更小的点，最后谁被拼接完了，就直接拼接另一条链表剩下的，这样不难看出，每次的步骤都是重复的，于是我们可以使用递归的思想来解决这道问题。

代码

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1) return list2;
        if(!list2) return list1;

        if(list1->val<=list2->val){
            list1->next=mergeTwoLists(list1->next,list2);
            return list1;
        }else{
            list2->next=mergeTwoLists(list2->next,list1);
            return list2;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1. 如果 list1 为空，说明第一个链表为空，直接返回 list2。
2. 如果 list2 为空，说明第二个链表为空，直接返回 list1。
3. 接下来比较 list1 和 list2 的头节点的值，选择较小的节点作为新链表的头节点。
4. 如果 list1 的头节点值小于等于 list2 的头节点值，将 list1 的下一个节点与 list2 合并，并返回 list1 作为新链表的头节点。
5. 如果 list2 的头节点值小于 list1 的头节点值，将 list2 的下一个节点与 list1 合并，并返回 list2 作为新链表的头节点。

03.反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
1
2

示例 2：

输入：head = [1,2]
输出：[2,1]
1
2

示例 3：

输入：head = []
输出：[]
1
2

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

思路

若我们直接遍历到最后的节点再逐个向前改变指向，在每次接入前一个节点时，将它的next指向空，最终返回头节点即可。

1. 递归函数的含义：交给你⼀个链表的头指针，你帮我逆序之后，返回逆序后的头结点；
2. 函数体：先把当前结点之后的链表逆序，逆序完之后，把当前结点添加到逆序后的链表后面即可；
3. 递归出口：当前结点为空或者当前只有⼀个结点的时候，不用逆序，直接返回

代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head||!head->next) return head;

        ListNode* newhead = reverseList(head->next);
        head->next->next=head;
        head->next=nullptr;

        return newhead;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

04.两两交换链表中的节点

题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]
1
2

示例 2：

输入：head = []
输出：[]
1
2

示例 3：

输入：head = [1]
输出：[1] 
1
2

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

思路

我们将问题划分为子问题，先交换当前节点的下两个节点，将当前节点的下一个节点作为新的头节点，将当前节点的下一个节点指向递归操作的结果，返回新的头节点。

代码

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        // 如果链表为空或者只有一个节点，无需交换，直接返回原链表头指针
        if (!head || !head->next)
            return head;

        // 递归调用，交换当前节点的下两个节点
        ListNode* tmp = swapPairs(head->next->next);
        
        // 将当前节点的下一个节点作为新的头节点
        ListNode* ret = head->next;
        
        // 将当前节点的下一个节点指向当前节点，实现交换
        head->next->next = head;
        
        // 将当前节点的下一个节点指向递归操作的结果
        head->next = tmp;

        // 返回新的头节点
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1. if (!head || !head->next)：检查链表是否为空或者只有一个节点。如果是，直接返回原链表头指针，因为不需要进行交换。
2. ListNode* tmp = swapPairs(head->next->next);：递归调用swapPairs函数，传入当前节点的下两个节点。这样就会从链表的末尾开始，每次交换两个相邻的节点，然后返回新的头节点。
3. ListNode* ret = head->next;：将当前节点的下一个节点作为新的头节点，因为在交换过程中，它会变成新的头节点。
4. head->next->next = head;：将当前节点的下一个节点指向当前节点，实现交换操作。
5. head->next = tmp;：将当前节点的下一个节点指向递归操作的结果，即当前节点的下两个节点交换后的头节点。
6. return ret;：返回新的头节点，作为上层递归调用的结果。

05.Pow(x, n)

题目链接：https://leetcode.cn/problems/powx-n/

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
1
2

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100
1
2

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
1
2
3

提示：

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• n 是一个整数
• 要么 x 不为零，要么 n > 0 。
• -104 <= xn <= 104

思路

这里我们可以使用二分的思想，可以快速提高效率，例如将3的32次方分为两个3的16次方相乘，不断向下递归，最终返回相乘结果，只不过这里需要注意负数和奇偶次方问题需要单独判断。

代码

class Solution {
public:
    double myPow(double x, int n) {
        // 如果指数n为负数，将问题转化为计算 x^(-n)，即取倒数
        return n < 0 ? 1.0 / Pow(x, -(long long)n) : Pow(x, n);
    }

    double Pow(double x, long long n) {
        // 递归终止条件：n为0时，任何数的0次方都为1
        if (n == 0) 
            return 1.0;
        
        // 递归调用，计算 x^(n/2)
        double tmp = Pow(x, n / 2);
        
        // 如果n为奇数，返回 tmp * tmp * x
        if (n % 2)
            return tmp * tmp * x;
        else // 如果n为偶数，返回 tmp * tmp
            return tmp * tmp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1. return n < 0 ? 1.0 / Pow(x, -(long long)n) : Pow(x, n);：根据指数n的正负情况，决定调用正指数或者取倒数的递归函数。当n为负数时，将其转化为正数计算，并返回结果的倒数。
2. double Pow(double x, long long n)：递归函数，用于计算 x^n。
3. if (n == 0) return 1.0;：递归终止条件。当指数n为0时，任何数的0次方都为1。
4. double tmp = Pow(x, n / 2);：递归调用，计算 x^(n/2)。这里利用了指数幂的性质，将问题规模减半，减少了计算量。
5. if (n % 2)：判断n是否为奇数。
6. return tmp * tmp * x;：如果n为奇数，返回 tmp * tmp * x，这是因为 x^n = (x^(n/2))2 * x。
   n) : Pow(x, n);`：根据指数n的正负情况，决定调用正指数或者取倒数的递归函数。当n为负数时，将其转化为正数计算，并返回结果的倒数。
7. double Pow(double x, long long n)：递归函数，用于计算 x^n。
8. if (n == 0) return 1.0;：递归终止条件。当指数n为0时，任何数的0次方都为1。
9. double tmp = Pow(x, n / 2);：递归调用，计算 x^(n/2)。这里利用了指数幂的性质，将问题规模减半，减少了计算量。
10. if (n % 2)：判断n是否为奇数。
11. return tmp * tmp * x;：如果n为奇数，返回 tmp * tmp * x，这是因为 x^n = (x^(n/2))2 * x。
12. return tmp * tmp;：如果n为偶数，返回 tmp * tmp，这是因为 x^n = (x^(n/2))2。