前言：递归算法在计算机科学中是一个既简单又强大的工具。通过函数调用自身，递归能帮助我们轻松解决许多看似复杂的问题，从经典的斐波那契数列，到更高阶的树形结构遍历。然而，递归的巧妙之处在于理解如何正确地定义“基准情况”和“递归情况”，从而确保算法的正确性和效率。本篇博客将带你从递归的基础概念入手，逐步深入探讨递归算法的应用及优化策略，帮助你在面试和实际编程中掌握这项必备技能。
算法思路： 重复子问题->函数头的设计
只关心某一个子问题在做什么事情->函数体的事情
递归的出口
【注意】：无条件相信自己的函数体一定能成功，不要深究
思考1：什么时候循环舒服，什么时候递归舒服？
如果递归的展开是单分支，就用循环，如果是多叉树，就用递归思考2：递归vs深搜
递归的展开图就是对一棵树做一次深度优先遍历（dfs）。🍰一、力扣21. 合并两个有序链表解法：基本情况处理： 如果链表 l1 为空（l1 == nullptr），则直接返回链表 l2 作为合并后的链表。如果链表 l2 为空（l2 == nullptr），则直接返回链表 l1 作为合并后的链表。递归调用： 比较 l1 和 l2 当前节点的值。如果 l1->val <= l2->val，说明 l1 当前节点的值应该在新链表的前面。此时，递归地调用 mergeTwoLists 函数，将 l1->next 和 l2 作为参数，并将返回的节点设置为 l1->next。然后返回 l1，因为 l1 当前节点是新链表的头节点或某个子链表的头节点。如果 l1->val > l2->val，则执行与上述相反的操作，即将 l2 当前节点放在新链表的前面，并递归地处理剩余部分。合并过程： 在每次递归调用中，都会确定当前两个链表中哪个节点的值应该在新链表的前面。通过递归，这个过程会一直进行到两个链表中的至少一个为空。递归返回时，每个节点的 next 指针都会被正确设置，指向合并后链表的下一个节点。返回结果： 最终，当递归调用达到基本情况时，会返回一个非空的链表头节点，这个节点是合并后链表的头节点。代码：代码语言：javascript代码运行次数：0运行复制/**
* 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再思考解法：基本情况处理： 如果链表为空（head == nullptr）或者链表中只有一个节点（head->next == nullptr），则无需进行反转，直接返回原链表头节点 head。递归调用： 递归地处理链表的剩余部分，即从 head->next 开始的链表。这里，reverseList(head->next) 会返回反转后链表的头节点，我们将其存储在 newnode 变量中。节点反转： 在当前递归层级，我们需要将 head 节点与 head->next 节点（现在已经是反转后链表的一部分）进行“局部”反转。将 head->next->next 设置为 head，这样 head 节点就被插入到了反转后链表的头部（但实际上，由于递归还未返回，这部分链表在递归栈中还未完全构建完成）。将 head->next 设置为 nullptr，因为 head 现在是反转后链表的最后一个节点。返回结果： 返回 newnode，即反转后链表的头节点。这个节点是递归调用返回的，代表了除当前 head 节点外，已经反转完成的链表部分。代码：代码语言：javascript代码运行次数：0运行复制/**
* 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. 两两交换链表中的节点解法：基本情况处理： 如果链表为空（head == nullptr）或者链表中只有一个节点（head->next == nullptr），则无需进行任何交换，直接返回原链表头节点 head。递归调用： 递归地处理从链表的第三个节点开始的剩余部分。这里使用 head->next->next 作为递归调用的参数，因为前两个节点（head 和 head->next）将在当前递归层级中被交换。递归调用的结果存储在 tmp 变量中，它代表了交换后的剩余链表的头节点。节点交换： ret 变量被设置为 head->next，即交换后的新链表的头节点（因为 head 和 head->next 交换位置后，head->next 将成为新的头节点）。接下来，将 head->next->next 指向 head，完成两个节点的交换。最后，将 head->next 设置为 tmp，即将交换后的剩余链表连接到已经交换好的前两个节点之后。返回结果： 返回 ret，即交换后的新链表的头节点。代码：代码语言：javascript代码运行次数：0运行复制/**
* 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)（快速幂）细节问题：递归：pow 函数通过递归的方式实现了幂的计算，每次递归都将问题的规模减半（计算 n/2 次幂），从而提高了效率。负指数处理：myPow 函数通过检查 n 的符号，并相应地调整计算方式，来处理负指数的情况。类型转换：在处理负指数时，将 n 转换为 long long 类型，以避免在取负时可能发生的整数溢出。解法：myPow 函数如果 n 大于 0，直接调用 pow 函数计算 x 的 n 次幂。如果 n 小于或等于 0，将 n 转换为正数（通过取负并转换为 long long 类型以避免整数溢出），然后计算 1 除以 x 的 -n 次幂，以此处理负指数的情况。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。代码：代码语言：javascript代码运行次数：0运行复制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. 汉诺塔问题解法： 重复子问题->函数头
将x柱子上的n个盘子，借助y柱子，转移到z柱子上去——void dfs(x, y, z, n); 只关心某一个子问题在做什么事情->函数体的事情
将x上的n-1个盘子，借助z柱子，转移到y柱子上去——dfs(x, z, y, n-1);
将x上剩余的最大的盘子转移到z柱子上去
再将y柱子上的n-1个盘子，借助x柱子，转移到z柱子上去——dfs(y, x, z, n-1);
递归的出口
当n = 1时，将x的最后一个盘子移到z柱子上去即可代码：代码语言：javascript代码运行次数：0运行复制class Solution {
public:
void dfs(vector
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 n = x.size();
dfs(x, y, z, n);
}
};结语递归不仅仅是一种解决问题的方式，更是培养编程思维的重要手段。通过本篇博客的学习，你已经了解了递归算法的核心概念和它在各种问题中的应用。掌握递归的思想，能够让你在面对复杂问题时找到更优雅、简洁的解决方案。在未来的编程旅程中，不妨多思考递归与迭代的选择，并不断优化你的递归算法，使之更高效、更具可扩展性。希望你通过这篇文章，对递归有了更深入的理解，并在之后的算法挑战中游刃有余。
今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，17的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是17前进的动