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

文章目录

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

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

前言

第一章：递归基础及应用

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 的情况。

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

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

动图讲解

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 均按非递减顺序排列

解法（递归）

算法思路

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

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

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

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

解法（递归）

算法思路

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

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

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]

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

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

易错点提示

处理负指数：
- 当 n 为负数时，将 x^(-n) 转换为 1/(x^n)。为避免溢出，将 n 转换为 long long 型。
递归出口：
- n == 0 时返回 1。这是递归求幂的基础条件。
避免重复计算：
- 递归过程中，pow(x, n / 2) 结果保存在 temp 中，减少重复计算。

时间复杂度和空间复杂度

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

写在最后

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

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

可分解性：问题可以划分为规模更小的子问题，并且这些子问题具有与原问题相同的解决方法。即问题具有相同的结构，可以递归处理。
递推关系：当我们知道规模更小的子问题（如 n - 1）的解时，能够通过递推关系直接计算出规模为 n 的问题的解。这种递推关系能够使得问题逐层缩小。
基本情况（终止条件）：问题存在一个简单的情况，当问题的规模足够小（如 n=0 或 n=1）时，可以直接给出结果，这作为递归的终止条件。

一般的递归求解过程

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

验证是否满足基本情况：检查是否到达递归终止条件，若满足则直接返回结果。
假设子问题已解决，解决当前问题：通过递归调用，将当前问题划分为规模更小的子问题，并假设子问题可以正确解决，根据子问题的解来解决当前问题。
递归证明的有效性：从较小规模的情况出发，逐步构建到较大规模的问题，可以使用数学归纳法证明递归的正确性。

五道题的递归应用分析

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

汉诺塔问题：在移动 n 个盘子时，将 n-1 个盘子移到中间柱作为子问题，递归解决剩余部分。简单情况为 n=1 时直接移动。
合并两个有序链表：通过递归合并剩余部分的链表并解决当前头节点。简单情况为某一链表为空时直接返回另一链表。
反转链表：递归将链表中剩余部分反转，并将当前节点放到反转结果之后。简单情况为链表为空或仅一个节点时直接返回。
两两交换链表中的节点：递归将后续链表的节点交换，并对当前两个节点进行交换。简单情况为链表为空或仅有一个节点时直接返回。
快速幂问题：使用递归对幂次进行二分计算，以减少计算次数，递归到 n=0 时返回 1。通过 n 的奇偶判断是否需要乘上额外的 x，从而完成快速幂。

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

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

Hoshiᅟᅠ