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

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

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

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

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

---

前言

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

---

第一章：递归基础及应用

1.1 汉诺塔问题（easy）

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

算法讲解

1. 当 n = 1 时，直接将 A 顶部的盘子移动到 C。
2. 当 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)。

---

易错点提示

1. 递归的终止条件

   • 一定要确保在 n = 1 时停止递归，否则会陷入死循环。递归的终止条件是递归正确执行的关键。

2. 参数顺序

   • 在递归调用中，要注意 A、B、C 的顺序变化，确保每次调用的目标柱子和辅助柱子正确。

3. 理解递归的分治思想

   • 每次递归调用都是将问题缩小为一个规模更小的子问题，直到无法再缩小。分治思想是递归解决复杂问题的核心理念。

4. 递归调用的顺序

   • 先处理子问题，再处理当前步骤，最后再处理另一个子问题，顺序不可颠倒。

5. 递归栈的深度控制

   • 如果递归层数太深，可能会导致栈溢出。因此在处理较大的 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 均按非递减顺序排列

---

解法（递归）

算法思路

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

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

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;}}
};

---

易错点提示：

1. 递归的出口：

   • 一定要处理好链表为空的情况，这是递归的出口条件。只有当某一个链表为空时，才能返回另一个链表。

2. 理解指针的变化：

   • 画出链表的指针图，可以帮助理解链表节点的变化以及递归过程中指针如何调整。链表指针的递归合并涉及指针的不断改变，清晰的画图可以有效避免混乱。

3. 递归函数的设计：

   • 递归函数的核心是不断比较两个链表的头节点，选择较小的节点作为合并后的链表的当前节点，并递归处理剩余部分。

---

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

• 时间复杂度：

  • 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

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

---

解法（递归）

算法思路

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

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

---

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;}
};

---

易错点提示：

1. 递归的出口：

   • 当链表为空或者只有一个节点时，不需要再进行反转，直接返回。这是递归的基础条件。

2. 指针操作理解：

   • 需要注意指针的操作：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

---

解法（递归）

算法思路

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

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

---

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;}
};

---

易错点提示

1. 递归的出口：

   • 当链表为空或只剩一个节点时，不需要进行交换操作。这是递归的基础条件。

2. 指针操作：

   • 需要注意指针的正确连接顺序。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

---

解法（递归 - 快速幂）

算法思路

1. 递归函数的含义：计算 x 的 n 次方并返回结果。
2. 函数体：先求出 x 的 n/2 次方，然后根据 n 的奇偶性来决定最终结果：
   • 如果 n 是偶数，则 x^n = (x^(n/2)) * (x^(n/2))
   • 如果 n 是奇数，则 x^n = (x^(n/2)) * (x^(n/2)) * x
3. 递归出口：当 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;}
};

---

易错点提示

1. 处理负指数：

   • 当 n 为负数时，将 x^(-n) 转换为 1/(x^n)。为避免溢出，将 n 转换为 long long 型。

2. 递归出口：

   • n == 0 时返回 1。这是递归求幂的基础条件。

3. 避免重复计算：

   • 递归过程中，pow(x, n / 2) 结果保存在 temp 中，减少重复计算。

---

时间复杂度和空间复杂度

• 时间复杂度：O(log n)，每次递归将 n 减半，因此复杂度为对数级。
• 空间复杂度：O(log n)，递归栈的深度为 O(log n)。

---

写在最后

总结：递归解题的核心思路

在解决一个规模为 n 的问题时，递归方法的应用通常需要满足以下三个条件：

1. 可分解性：问题可以划分为规模更小的子问题，并且这些子问题具有与原问题相同的解决方法。即问题具有相同的结构，可以递归处理。

2. 递推关系：当我们知道规模更小的子问题（如 n - 1）的解时，能够通过递推关系直接计算出规模为 n 的问题的解。这种递推关系能够使得问题逐层缩小。

3. 基本情况（终止条件）：问题存在一个简单的情况，当问题的规模足够小（如 n=0 或 n=1）时，可以直接给出结果，这作为递归的终止条件。

---

一般的递归求解过程

递归解题的过程通常如下：

1. 验证是否满足基本情况：检查是否到达递归终止条件，若满足则直接返回结果。

2. 假设子问题已解决，解决当前问题：通过递归调用，将当前问题划分为规模更小的子问题，并假设子问题可以正确解决，根据子问题的解来解决当前问题。

3. 递归证明的有效性：从较小规模的情况出发，逐步构建到较大规模的问题，可以使用数学归纳法证明递归的正确性。

---

五道题的递归应用分析

结合本专题的五道递归问题，我们可以看到不同的递归应用模式：

1. 汉诺塔问题：在移动 n 个盘子时，将 n-1 个盘子移到中间柱作为子问题，递归解决剩余部分。简单情况为 n=1 时直接移动。

2. 合并两个有序链表：通过递归合并剩余部分的链表并解决当前头节点。简单情况为某一链表为空时直接返回另一链表。

3. 反转链表：递归将链表中剩余部分反转，并将当前节点放到反转结果之后。简单情况为链表为空或仅一个节点时直接返回。

4. 两两交换链表中的节点：递归将后续链表的节点交换，并对当前两个节点进行交换。简单情况为链表为空或仅有一个节点时直接返回。

5. 快速幂问题：使用递归对幂次进行二分计算，以减少计算次数，递归到 n=0 时返回 1。通过 n 的奇偶判断是否需要乘上额外的 x，从而完成快速幂。

递归是一种强大且高效的编程技巧，能够将复杂的问题化简为小规模的同类问题。使用递归时，确保问题满足可分解性、递推关系和基本情况，并严格控制递归的终止条件，以保证算法的正确性和高效性。

---

以上就是关于【递归回溯与搜索算法篇】算法的镜花水月：在无尽的自我倒影中，递归步步生花的内容啦，各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️