✨✨✨学习的道路很枯燥，希望我们能并肩走下来!
目录
前言
作为递归、搜索与回溯算法系列的第一篇，本篇详细介绍了递归算法的使用，让使用者了解递归运算，而不是仅仅停留在表面， 文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！
一 深入理解递归
二 迭代VS递归
三 递归算法题目解析
3.1 汉诺塔问题
面试题 08.06. 汉诺塔问题 - 力扣（LeetCode）
我们简单取1到4个圆盘进行移动，我们从宏观角度发现这是一个重复子问题
class Solution {
public:
void move(vector<int>& A, vector<int>& B, vector<int>& C,int n)
{
if(n == 1)
{
C.push_back(A.back());
A.pop_back();
return;
}
move(A,C,B,n-1);
C.push_back(A.back());
A.pop_back();
move(B,A,C,n-1);
}
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
int n = A.size();
move(A,B,C,n);
}
};如果我们在笔试中遇到的，只需要保证能通过就行
不讲武德版：
class Solution {
public:
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
C = A;
}
};3.2 合并两个有序链表
我们之前是使用迭代（循环）来做的
迭代：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
ListNode* l1 = list1;
ListNode* l2 = list2;
ListNode* newHead = NULL;
ListNode* newTail = NULL;
newHead = newTail = (ListNode*)malloc(sizeof(ListNode));
if(l1==NULL)
{
return l2;
}
if(l2==NULL)
{
return l1;
}
while(l1&&l2)
{
if(l1->val<l2->val)
{
newTail->next=l1;
newTail=newTail->next;
l1=l1->next;
}
else
{
newTail->next=l2;
newTail=newTail->next;
l2=l2->next;
}
}
if(l1)
{
newTail->next=l1;
}
else
{
newTail->next=l2;
}
ListNode* ret = newHead->next;
free(newHead);
return 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1 == nullptr) return list2;
if(list2 == nullptr) return list1;
if(list1->val <= list2->val)
{
list1->next = mergeTwoLists(list1->next,list2);
return list1;
}
else
{
list2->next = mergeTwoLists(list1,list2->next);
return list2;
}
}
};3.3 反转链表
/**
* 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;
}
};3.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* swapPairs(ListNode* head) {
if(head == nullptr || head->next == nullptr) return head;
auto newNode = swapPairs(head->next->next);
auto ret = head->next;
head->next->next = head;
head->next = newNode;
return ret;
}
};3.5 Pow（x，n）（快速幂)
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 tmp = Pow(x,n/2);
return n%2 == 0 ? tmp*tmp : tmp*tmp*x;
}
};用long long避免int无法存n为2的-31次方
四 总结
1. 从题目发掘出重复的子问题
2. 只针对某一子问题考虑解决方法
3. 注意递归出口
总结
✨✨✨各位读友，本篇分享到内容是否更好的让你理解递归算法，如果对你有帮助给个
标签：head,ListNode,val,递归,int,迷宫,next,算法,return From： https://blog.csdn.net/2301_79691881/article/details/139832413