当前位置：首页 > article >正文

【递归回溯与搜索算法篇】算法的镜花水月：在无尽的自我倒影中，递归步步生花

article 2024/11/16 8:03:18

文章目录

递归回溯搜索专题（一）：递归
- 前言
- 第一章：递归基础及应用
- - 1.1 汉诺塔问题（easy）
  - - 解法（递归）
    - C++ 代码实现
    - 时间复杂度和空间复杂度
    - 易错点提示
  - 1.2 合并两个有序链表（easy）
  - - 解法（递归）
    - C++ 代码实现
    - 易错点提示：
    - 时间复杂度和空间复杂度：
  - 1.3 反转链表（easy）
  - - 解法（递归）
    - C++ 代码实现
    - 易错点提示：
    - 时间复杂度和空间复杂度：
  - 1.4 两两交换链表中的节点（medium）
  - - 解法（递归）
    - C++ 代码实现
    - 易错点提示
    - 时间复杂度和空间复杂度：
  - 1.5 Pow(x, n) - 快速幂（medium）
  - - 解法（递归 - 快速幂）
    - C++ 代码实现
    - 易错点提示
    - 时间复杂度和空间复杂度
- 写在最后
- - 总结：递归解题的核心思路
  - 一般的递归求解过程
  - 五道题的递归应用分析

递归回溯搜索专题（一）：递归

🚀 欢迎讨论：如果你有任何问题或者想法，欢迎在评论区留言。

👍 点赞、收藏与分享：如果你觉得这篇文章对你有帮助，请点赞、收藏并分享给更多朋友。

💡 分享更多人：一起学习递归与回溯，掌握解题的关键技能！

前言

在编程的世界中，递归就像是一扇通往无限的门，你站在门前，可以看到镜中无数的自己。它的力量在于用简单的重复动作，解决复杂的结构问题。这篇文章将带你走进递归的世界，帮助你掌握这一强大且充满魔力的工具。我们会逐步拆解递归的基本概念，通过具体的题目来深入理解它的精髓。

第一章：递归基础及应用

1.1 汉诺塔问题（easy）

题目链接：面试题 08.06 汉诺塔问题

题目描述：

在经典汉诺塔问题中，有 3 根柱子和 N 个不同大小的穿孔圆盘。圆盘可以滑入任意一根柱子。初始状态下，所有圆盘自上而下按升序叠在第一根柱子上，任务是将所有圆盘从第一根柱子移到最后一根柱子，满足以下限制：

每次只能移动一个圆盘。
盘子只能从柱子顶端滑出，移到下一根柱子。
盘子只能叠在比它大的盘子上。

示例1：

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

示例2：

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

提示：A 中盘子的数目不大于 14 个。

解法（递归）

算法思路

汉诺塔是递归的经典题目，我们可以从最简单的情况入手：

假设 n = 1，只有一个盘子，直接把它从 A 移到 C 即可；
如果 n = 2，我们需要借助 B 柱完成三步操作：
1. 把小盘子从 A 移到 B；
2. 把大盘子从 A 移到 C；
3. 再把小盘子从 B 移到 C。

对于 n > 2，我们需要将 A 上面的 n-1 个盘子移动到 B，再将最大的盘子移动到 C，最后把 B 上的 n-1 个盘子移动到 C。递归就是不断把问题缩小到 n = 1 的情况。

为了帮助更好地理解汉诺塔问题，可以使用以下动画演示，展示了盘子如何一步步从起始柱移动到目标柱：

在这里插入图片描述

动图讲解

动图中展示了汉诺塔的移动过程，可以看到每一步的移动都是将问题拆分成子问题，先解决上方的小盘子，再移动大盘子，最后再将小盘子放到目标位置。这种“拆解-解决-合并”的思路就是递归的核心。

C++ 代码实现

递归函数设计：

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        dfs(A, B, C, A.size());
    }

    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);   // Step 1: 将 A 上面的 n-1 个盘子移到 B
        C.push_back(A.back()); // Step 2: 将 A 上的最大盘子移到 C
        A.pop_back();
        dfs(B, A, C, n - 1); // Step 3: 将 B 上的 n-1 个盘子移到 C
    }
};

算法讲解

当 n = 1 时，直接将 A 顶部的盘子移动到 C。
当 n > 1 时，首先递归地将 A 顶部的 n-1 个盘子移到 B，然后将 A 顶部的一个盘子移到 C，最后将 B 上的 n-1 个盘子移到 C。

详细步骤举例

对于 n = 3 的情况：
1. 将 A 上的 2 个盘子移到 B（递归调用）。
2. 将 A 上剩下的最大盘子移到 C。
3. 将 B 上的 2 个盘子移到 C（递归调用）。

每一步的操作都严格遵循递归的逻辑，先处理子问题，再处理当前问题，最后合并结果。

时间复杂度和空间复杂度

时间复杂度
- 汉诺塔问题的时间复杂度为 O(2^n)。
- 递推关系为 T(n) = 2T(n-1) + 1，通过递归不断展开可得到 T(n) = 2^n - 1，因此时间复杂度为 O(2^n)。这是由于每个盘子的移动都依赖于之前所有的盘子，每次递归拆分问题的数量呈指数级增长。
空间复杂度
- 空间复杂度为 O(n)，主要来自递归调用栈的深度。每一次递归调用都会占用栈空间，最大递归深度为 n，因此空间复杂度为 O(n)。

易错点提示

递归的终止条件
- 一定要确保在 n = 1 时停止递归，否则会陷入死循环。递归的终止条件是递归正确执行的关键。
参数顺序
- 在递归调用中，要注意 A、B、C 的顺序变化，确保每次调用的目标柱子和辅助柱子正确。
理解递归的分治思想
- 每次递归调用都是将问题缩小为一个规模更小的子问题，直到无法再缩小。分治思想是递归解决复杂问题的核心理念。
递归调用的顺序
- 先处理子问题，再处理当前步骤，最后再处理另一个子问题，顺序不可颠倒。
递归栈的深度控制
- 如果递归层数太深，可能会导致栈溢出。因此在处理较大的 n 值时要格外注意递归的深度，考虑优化或改为迭代解决方案。

1.2 合并两个有序链表（easy）

题目链接：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 <= 100
l1 和 l2 均按非递减顺序排列

解法（递归）

算法思路

递归函数的含义：交给你两个链表的头节点，你帮我把它们合并起来，并且返回合并后的头节点。
函数体：选择两个头节点中较小的节点作为最终合并后的头节点，然后将剩下的链表交给递归函数去处理。
递归出口：当某一个链表为空的时候，返回另外一个链表。

注意：链表的题目一定要画图，搞清楚指针的操作！
在这里插入图片描述

C++ 代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;

        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

易错点提示：

递归的出口：
- 一定要处理好链表为空的情况，这是递归的出口条件。只有当某一个链表为空时，才能返回另一个链表。
理解指针的变化：
- 画出链表的指针图，可以帮助理解链表节点的变化以及递归过程中指针如何调整。链表指针的递归合并涉及指针的不断改变，清晰的画图可以有效避免混乱。
递归函数的设计：
- 递归函数的核心是不断比较两个链表的头节点，选择较小的节点作为合并后的链表的当前节点，并递归处理剩余部分。

时间复杂度和空间复杂度：

时间复杂度：
- O(n + m)，其中 n 和 m 分别是两个链表的长度。需要遍历两个链表的所有节点才能完成合并。
空间复杂度：
- O(n + m)，递归的深度取决于两个链表的长度。在最坏情况下，递归调用的深度为 n + m，因此空间复杂度为 O(n + m)。

1.3 反转链表（easy）

题目链接：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

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

解法（递归）

算法思路

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

注意：链表的题目一定要画图，搞清楚指针的操作！

在这里插入图片描述

C++ 代码实现

/*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

易错点提示：

递归的出口：
- 当链表为空或者只有一个节点时，不需要再进行反转，直接返回。这是递归的基础条件。
指针操作理解：
- 需要注意指针的操作：head->next->next = head 这一步是将当前节点接在逆序链表的后面，同时要断开当前节点的 next（即 head->next = nullptr），否则会产生环。

时间复杂度和空间复杂度：

时间复杂度：
- O(n)，其中 n 是链表的长度。每个节点遍历一次。
空间复杂度：
- O(n)，递归调用的深度为 n，因此需要 O(n) 的栈空间。

1.4 两两交换链表中的节点（medium）

题目链接：24. 两两交换链表中的节点

题目描述：

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

示例1：

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

在这里插入图片描述

示例2：

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

示例3：

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

提示：

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

解法（递归）

算法思路

递归函数的含义：给定一个链表，将其两两交换，并返回交换后的头结点。
函数体：先处理第二个节点后的链表，得到其交换后的头节点，然后将当前两个节点交换并连接到后面处理后的链表。
递归出口：当当前节点为空或者只有一个节点时，不需要交换，直接返回当前节点。

注意：链表的题目一定要画图，确保理解指针的操作。

C++ 代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        
        auto nextPair = swapPairs(head->next->next);  // 处理后面的链表
        auto newHead = head->next;                    // 第二个节点作为新头节点
        newHead->next = head;                         // 交换当前两个节点
        head->next = nextPair;                        // 连接到后面交换后的链表
        
        return newHead;
    }
};

易错点提示

递归的出口：
- 当链表为空或只剩一个节点时，不需要进行交换操作。这是递归的基础条件。
指针操作：
- 需要注意指针的正确连接顺序。newHead->next = head 将当前两个节点交换；head->next = nextPair 将交换后的头节点连接到后面处理后的链表。

时间复杂度和空间复杂度：

时间复杂度：O(n)，其中 n 是链表的长度。每次递归处理两个节点，共递归 n/2 次。
空间复杂度：O(n)，递归深度为 n/2。

1.5 Pow(x, n) - 快速幂（medium）

题目链接：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/2^2 = 1/4 = 0.25

提示：

-100.0 < x < 100.0
-2^31 <= n <= 2^31 - 1
n 是一个整数
要么 x 不为零，要么 n > 0
-10^4 <= x^n <= 10^4

解法（递归 - 快速幂）

算法思路

递归函数的含义：计算 x 的 n 次方并返回结果。
函数体：先求出 x 的 n/2 次方，然后根据 n 的奇偶性来决定最终结果：
- 如果 n 是偶数，则 x^n = (x^(n/2)) * (x^(n/2))
- 如果 n 是奇数，则 x^n = (x^(n/2)) * (x^(n/2)) * x
递归出口：当 n 为 0 时，返回 1，因为任何数的 0 次幂都是 1。

C++ 代码实现

class Solution {
public:
    double myPow(double x, int n) {
        return n < 0 ? 1.0 / pow(x, -(long long)n) : pow(x, n);
    }
    
    double pow(double x, long long n) {
        if (n == 0) return 1.0;
        double temp = pow(x, n / 2);
        return n % 2 == 0 ? temp * temp : temp * temp * x;
    }
};