递归算法在计算机科学中是一个既简单又强大的工具。通过函数调用自身,递归能帮助我们轻松解决许多看似复杂的问题,从经典的斐波那契数列,到更高阶的树形结构遍历。然而,递归的巧妙之处在于理解如何正确地定义“基准情况”和“递归情况”,从而确保算法的正确性和效率。本篇博客将带你从递归的基础概念入手,逐步深入探讨递归算法的应用及优化策略,帮助你在面试和实际编程中掌握这项必备技能。
【注意】:无条件相信自己的函数体一定能成功,不要深究
思考1:什么时候循环舒服,什么时候递归舒服?
思考2:递归vs深搜
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
指针都会被正确设置,指向合并后链表的下一个节点。/**
* 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;
}
}
};
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
节点外,已经反转完成的链表部分。/**
* 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;
}
};
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
,即交换后的新链表的头节点。/**
* 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;
}
};
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。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;
}
};
void dfs(x, y, z, n);
dfs(x, z, y, n-1);
dfs(y, x, z, n-1);
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前进的动