引言
通过递归的视角，来宏观看待一些问题，从而深入了解递归，为搜索打下基础。
一、汉诺塔
思路：
- 函数头设计：把x柱子上的n个盘子，以y柱子为辅助，转移到z柱子上
- 先将x上n-1个盘子移到y上，再将x上最下面的盘子移到z，最后再将y上n-1个盘子移到z上
- 终止条件：当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();
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>& A, vector<int>& B, vector<int>& C)
{
dfs(A, B, C, A.size());
}
};
二、合并两个升序链表
思路：
- 先比较 l1 和 l2 头结点值的大小
- 选取较小的结点，将其下一个节点和另一个链表头结点进行合并
- 终止条件：当一个链表头结点为空时，返回另一个链表头结点
class Solution
{
public:
ListNode* dfs(ListNode* l1, ListNode* l2)
{
if(l1 == nullptr) return l2;
if(l2 == nullptr) return l1;
if(l1->val <= l2->val)
{
l1->next = dfs(l1->next, l2);
return l1;
}
else
{
l2->next = dfs(l1, l2->next);
return l2;
}
}
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{
return dfs(list1, list2);
}
};
三、反转链表
思路：
- 先将链表头结点的下一位进行反转，再将当前头结点链接在反转链表的尾部
- 终止条件：头结点为空，或只有一个节点
class Solution
{
public:
ListNode* dfs(ListNode* head)
{
if(!head || !head->next) return head;
ListNode* rhead = dfs(head->next);
head->next->next = head;
head->next = nullptr;
return rhead;
}
ListNode* reverseList(ListNode* head)
{
return dfs(head);
}
};
四、两两交换链表的结点
思路：
- 先将头两个结点后的结点进行两两交换，再将头两个结点进行交换
- 终止条件：头结点为空，或只有一个节点
class Solution
{
public:
ListNode* dfs(ListNode* head)
{
if(!head || !head->next) return head;
ListNode* newhead = dfs(head->next->next);
ListNode* next = head->next;
next->next = head;
head->next = newhead;
return next;
}
ListNode* swapPairs(ListNode* head)
{
return dfs(head);
}
};
五、Pow(x, n)
思路：
- 快速幂：时间复杂度为O(logN)，普通方法O(N)会超时
- 先算出n/2的幂tmp，再判断n是否为偶数，若为偶数，则返回tmp * tmp，若为奇数，则返回 tmp * tmp * x
- 终止条件：若n==0，则返回1（任何数的0次方都为1）
- 若n < 0，则计算1 / dfs(x, -n)（注意-n可能会数据溢出，所以改成long long）
class Solution
{
public:
double dfs(double x, long long n)
{
if(n == 0) return 1;
auto tmp = dfs(x, n/2);
return n%2==0 ? tmp*tmp : tmp*tmp*x;
}
double myPow(double x, long long n)
{
return n>=0 ? dfs(x, n) : 1/dfs(x, -n);
}
};
总结
对于一个重复的子问题，我们既可以用迭代（循环），也可以用递归。
递归的展开图，其实就是对一棵树进行深度优先遍历（dfs）
那么，什么时候用迭代舒服，什么时候用递归舒服呢？
- 当重复子问题只有一个分支时，用循环合适
- 当重复子问题有多个分支，用递归合适
