文章目录
- 引言
- 一、汉诺塔
- 二、合并两个升序链表
- 三、反转链表
- 四、两两交换链表的结点
- 五、Pow(x, n)
- 总结
引言
通过递归的视角，来宏观看待一些问题，从而深入了解递归，为搜索打下基础。
一、汉诺塔
思路：
- 函数头设计：把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）
那么，什么时候用迭代舒服，什么时候用递归舒服呢？
- 当重复子问题只有一个分支时，用循环合适
- 当重复子问题有多个分支，用递归合适
