递归算法的魔力：从基础到进阶的深入解析

前言：

递归算法在计算机科学中是一个既简单又强大的工具。通过函数调用自身，递归能帮助我们轻松解决许多看似复杂的问题，从经典的斐波那契数列，到更高阶的树形结构遍历。然而，递归的巧妙之处在于理解如何正确地定义“基准情况”和“递归情况”，从而确保算法的正确性和效率。本篇博客将带你从递归的基础概念入手，逐步深入探讨递归算法的应用及优化策略，帮助你在面试和实际编程中掌握这项必备技能。

算法思路：

1. 重复子问题->函数头的设计
2. 只关心某一个子问题在做什么事情->函数体的事情
3. 递归的出口

【注意】：无条件相信自己的函数体一定能成功，不要深究

思考1：什么时候循环舒服，什么时候递归舒服？

• 如果递归的展开是单分支，就用循环，如果是多叉树，就用递归

思考2：递归vs深搜

• 递归的展开图就是对一棵树做一次深度优先遍历（dfs）。

🍰一、力扣21. 合并两个有序链表

解法：

1. 基本情况处理：
   • 如果链表 l1 为空（l1 == nullptr），则直接返回链表 l2 作为合并后的链表。
   • 如果链表 l2 为空（l2 == nullptr），则直接返回链表 l1 作为合并后的链表。
2. 递归调用：
   • 比较 l1 和 l2 当前节点的值。
   • 如果 l1->val <= l2->val，说明 l1 当前节点的值应该在新链表的前面。此时，递归地调用 mergeTwoLists 函数，将 l1->next 和 l2 作为参数，并将返回的节点设置为 l1->next。然后返回 l1，因为 l1 当前节点是新链表的头节点或某个子链表的头节点。
   • 如果 l1->val > l2->val，则执行与上述相反的操作，即将 l2 当前节点放在新链表的前面，并递归地处理剩余部分。
3. 合并过程：
   • 在每次递归调用中，都会确定当前两个链表中哪个节点的值应该在新链表的前面。
   • 通过递归，这个过程会一直进行到两个链表中的至少一个为空。
   • 递归返回时，每个节点的 next 指针都会被正确设置，指向合并后链表的下一个节点。
4. 返回结果：
   • 最终，当递归调用达到基本情况时，会返回一个非空的链表头节点，这个节点是合并后链表的头节点。

代码：

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

🍰二、力扣206. 反转链表

视角1：从宏观角度看待问题

• 让当前结点后面的链表先逆置，并且把头结点返回
• 让当前结点添加到逆置后的链表后面即可

视角2：将链表看成一棵树

• 仅需做一次dfs即可
• 后序遍历找到叶子结点为止，然后结合视角1再思考

解法：

1. 基本情况处理：
   • 如果链表为空（head == nullptr）或者链表中只有一个节点（head->next == nullptr），则无需进行反转，直接返回原链表头节点 head。
2. 递归调用：
   • 递归地处理链表的剩余部分，即从 head->next 开始的链表。这里，reverseList(head->next) 会返回反转后链表的头节点，我们将其存储在 newnode 变量中。
3. 节点反转：
   • 在当前递归层级，我们需要将 head 节点与 head->next 节点（现在已经是反转后链表的一部分）进行“局部”反转。
   • 将 head->next->next 设置为 head，这样 head 节点就被插入到了反转后链表的头部（但实际上，由于递归还未返回，这部分链表在递归栈中还未完全构建完成）。
   • 将 head->next 设置为 nullptr，因为 head 现在是反转后链表的最后一个节点。
4. 返回结果：
   • 返回 newnode，即反转后链表的头节点。这个节点是递归调用返回的，代表了除当前 head 节点外，已经反转完成的链表部分。

代码：

/**
 * 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* newnode = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        
        return newnode;
    }
};

🍰三、力扣24. 两两交换链表中的节点

解法：

1. 基本情况处理：
   • 如果链表为空（head == nullptr）或者链表中只有一个节点（head->next == nullptr），则无需进行任何交换，直接返回原链表头节点 head。
2. 递归调用：
   • 递归地处理从链表的第三个节点开始的剩余部分。这里使用 head->next->next 作为递归调用的参数，因为前两个节点（head 和 head->next）将在当前递归层级中被交换。
   • 递归调用的结果存储在 tmp 变量中，它代表了交换后的剩余链表的头节点。
3. 节点交换：
   • ret 变量被设置为 head->next，即交换后的新链表的头节点（因为 head 和 head->next 交换位置后，head->next 将成为新的头节点）。
   • 接下来，将 head->next->next 指向 head，完成两个节点的交换。
   • 最后，将 head->next 设置为 tmp，即将交换后的剩余链表连接到已经交换好的前两个节点之后。
4. 返回结果：
   • 返回 ret，即交换后的新链表的头节点。

代码：

/**
 * 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;

        ListNode* tmp = swapPairs(head->next->next);
        ListNode* ret = head->next;
        head->next->next = head;
        head->next = tmp;
        
        return ret;
    }
};

🍰四、力扣50. Pow(x, n)（快速幂）

细节问题：

1. 递归：pow 函数通过递归的方式实现了幂的计算，每次递归都将问题的规模减半（计算 n/2 次幂），从而提高了效率。
2. 负指数处理：myPow 函数通过检查 n 的符号，并相应地调整计算方式，来处理负指数的情况。
3. 类型转换：在处理负指数时，将 n 转换为 long long 类型，以避免在取负时可能发生的整数溢出。

解法：

1. myPow 函数

• 如果 n 大于 0，直接调用 pow 函数计算 x 的 n 次幂。
• 如果 n 小于或等于 0，将 n 转换为正数（通过取负并转换为 long long 类型以避免整数溢出），然后计算 1 除以 x 的 -n 次幂，以此处理负指数的情况。

1. pow 函数

• 如果 n 等于 0，根据幂的定义，任何数的 0 次幂都是 1，所以直接返回 1。
• 使用递归的方式计算幂。首先计算x的n/2次幂，存储在tmp中。
  • 如果 n 是偶数，那么 x^n = (x^(n/2))^2，即 tmp * tmp。
  • 如果 n 是奇数，那么 x^n = x * (x^(n/2))^2，即 tmp * tmp * x。

代码：

class Solution {
public:
    double myPow(double x, int n) {
        return n > 0? pow(x, n): 1/pow(x, -(long long)n);     
    }

    double pow(double x, long long n){
        if(n == 0) return 1;

        double tmp = pow(x, n/2);
        return n % 2 == 0? tmp * tmp: tmp * tmp * x; 
    }
};

🍰五、力扣面试题 08.06. 汉诺塔问题

解法：

1. 重复子问题->函数头
   • 将x柱子上的n个盘子，借助y柱子，转移到z柱子上去——void dfs(x, y, z, n);
2. 只关心某一个子问题在做什么事情->函数体的事情
   • 1. 将x上的n-1个盘子，借助z柱子，转移到y柱子上去——dfs(x, z, y, n-1);
     2. 将x上剩余的最大的盘子转移到z柱子上去
     3. 再将y柱子上的n-1个盘子，借助x柱子，转移到z柱子上去——dfs(y, x, z, n-1);
3. 递归的出口
   • 当n = 1时，将x的最后一个盘子移到z柱子上去即可

代码：

class Solution {
public:
    void dfs(vector<int>& x, vector<int>& y, vector<int>& z, int n){
        if(n == 1){
            z.push_back(x.back());
            x.pop_back();	// 不要忘记清除x柱子上已经转移的盘子
            return;
        } 
        dfs(x, z, y, n - 1);
        
        z.push_back(x.back());
        x.pop_back();

        dfs(y, x, z, n - 1);
    }
    void hanota(vector<int>& x, vector<int>& y, vector<int>& z) {
        int n = x.size();
        dfs(x, y, z, n);
    }
};

结语

递归不仅仅是一种解决问题的方式，更是培养编程思维的重要手段。通过本篇博客的学习，你已经了解了递归算法的核心概念和它在各种问题中的应用。掌握递归的思想，能够让你在面对复杂问题时找到更优雅、简洁的解决方案。在未来的编程旅程中，不妨多思考递归与迭代的选择，并不断优化你的递归算法，使之更高效、更具可扩展性。希望你通过这篇文章，对递归有了更深入的理解，并在之后的算法挑战中游刃有余。 今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，17的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是17前进的动