算法训练之递归（一)

♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥♥♥♥我们一起努力成为更好的自己~♥♥♥♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥✨✨✨✨✨✨ 个人主页✨✨✨✨✨✨小伙伴们好久不见今天这一篇博客主要是递归算法的学习与练习~准备好了吗~我们发车去探索算法的奥秘啦~目录一、递归简单介绍1.1什么是递归1.2为什么能用递归1.3怎么理解递归1.4如何写好一个递归1.5递归模板1.6递归举例二、递归题目练习2.1合并两个有序链表2.2两两交换链表中的节点一、递归简单介绍1.1什么是递归递归就是函数自己调用自己去解决一个和原问题结构相同、规模更小的子问题。所以递归特别适合处理这类场景二叉树、快排、归并排序、分治问题一层套一层的结构。在之前二叉树阶段遍历就是使用递归来做的~1.2为什么能用递归递归能成立本质上是因为1.原问题可以拆成若干个相同性质的子问题比如遍历一棵树→ 遍历左子树 遍历右子树排序一个数组→ 排序左半部分 排序右半部分求阶乘→n! n × (n-1)!也就是说当前问题怎么做子问题还是怎么做。2.子问题规模在不断缩小递归不是无限调用而是每次都往更小的问题走。树→ 走到叶子节点数组→ 区间越来越小数字→ n 变成 n-13.一定要有“出口”没有出口递归就会一直调用下去最后栈溢出。所以递归一定包含两部分递归体把问题拆小继续调用自己递归出口什么时候停下来进行返回。1.3怎么理解递归不要过度纠结每一层是怎么展开的我们把递归函数当成一个黑盒【宏观思维】只关心当前这一层要做什么。初学递归时最容易卡住的点就是“这一步进去之后到底发生了什么”“它怎么回来”“为什么先算这个再算那个”。但是我们不用每层都死扣有一种更加巧妙的方法。我们相信这个函数只要收到一个更小的子问题它就一定能把那个子问题解决掉比如dfs(root-left);不用老想着它里面展开了多少层只要相信它能完成“把左子树处理完”。写递归时只想一件事假设子问题已经能解决那么当前问题怎么利用子问题的结果1.4如何写好一个递归第一步先找“相同的子问题”先问自己原问题能不能拆成和自己一样的更小问题比如二叉树遍历遍历整棵树本质就是遍历左子树、遍历右子树。第二步只写“当前层”的逻辑不要一上来就想 10 层之后会怎样只想这一层该处理什么子问题交给递归函数自己去做。第三步写清楚出口出口通常是空节点、区间长度为 1、n 0 或 n 1出口一定要简单、明确【具体问题具体分析】。1.5递归模板递归代码一般都长这样有时当前层逻辑在前有时在后取决于题目。void func(参数) { // 1. 递归出口 if (满足结束条件) return; // 2. 处理子问题 func(更小的参数); // 3. 当前层逻辑 }1.6递归举例还记得我们之前写到的阶乘吗接下来我们就用递归来解决~第一步先找“相同的子问题”先问自己原问题能不能拆成和自己一样的更小问题对于阶乘来说要求n!根据数学定义可以写成n! n × (n-1)!。也就是说要求n!这个大问题本质上先要解决(n-1)!这个更小的问题而(n-1)!和n!又是同一种类型的问题所以阶乘适合用递归来解决。第二步只写“当前层”的逻辑我们先不去想这个递归会展开多少层也不要急着想它最后是怎么一层层返回的只需要关注当前这一层该做什么。对于阶乘来说当前层要做的事情非常简单先把更小的子问题(n-1)!交给递归函数自己去求等它求出来以后当前层再用n × (n-1)!得到n!。所以当前层的逻辑就是return n * func(n - 1);。第三步写清楚出口递归一定要有结束条件否则函数会一直调用下去。对于阶乘来说最基本的出口就是当n 0或者n 1时阶乘的结果都等于1这时就不需要再继续递归可以直接返回结果1。因此出口可以写成if (n 0 || n 1) return 1;。实现代码#include iostream int func(int n) { //递归出口 if (n 1 || n 0) return 1; return n * func(n - 1);//当前层干什么 } int main() { std::cout 请输入数字; int t 0; std::cin t; std::cout t 的阶乘是 func(t) std::endl; return 0; }运行结果结果如我们所料知道了递归的大致思想接下来我们就需要利用递归去解决问题~二、递归题目练习2.1合并两个有序链表合并两个有序链表这个题目按照常规思路我们可以新建一个链表然后遍历两个链表进行比较在新链表后面进行连接现在如果我们想要利用递归解决这个问题呢我们按三步走来做第一步先找“相同的子问题”先来看看原问题能不能拆成和自己一样的更小问题这个题目要求的是“合并两个有序链表”假设现在我们要合并list1和list2。如果比较两个链表的头结点谁小谁就应该作为合并后链表的头结点。比如list1-val更小那么最终答案的头就是list1接下来要做的事情其实就变成了把list1-next和list2再合并起来。这就发现了一个“相同的子问题”——原问题是合并两个有序链表子问题仍然是合并两个有序链表只不过链表规模更小了一点。所以这个题目可以用递归。第二步只写“当前层”的逻辑我们不去想递归到底会展开多少层也不要急着想最后整个链表是怎么接起来的只需要关注当前这一层应该做什么。当前层的任务很简单先比较list1和list2的头结点值。如果list1-val list2-val说明当前这一层应该把list1这个节点接到结果链表前面然后它后面的部分交给递归函数去完成也就是让list1-next mergeTwoLists(list1-next, list2)如果list2-val更小那么就把list2接到结果链表前面再去递归合并list2-next和list1。所以当前层只做一件事选出较小的头结点并把剩下的合并任务交给递归。第三步写清楚出口递归一定要有结束条件。对于这个题目来说出口非常自然如果其中一个链表已经空了那么就不用再比较了直接返回另一个链表即可。因为另一个链表本身就是有序的直接接到后面就是最终结果。所以出口就是当list1 nullptr时返回list2当list2 nullptr时返回list1。这就是递归停止的条件。这个题目递归本质就是从两个链表头里选一个更小的当当前节点剩下部分继续合并。代码实现//合并两个有序链表 /** * 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(list2-next, list1); return list2; } } };运行结果顺利通过~2.2两两交换链表中的节点两两交换链表中的节点第一步先找“相同的子问题”先来看看原问题能不能拆成和自己一样的更小问题这个题要求的是“把链表中的节点两两交换”。假设现在链表长这样1 - 2 - 3 - 4我们先只看前两个节点1和2它们交换之后会变成2 - 1。那后面的部分3 - 4怎么办呢其实后面的部分仍然是同样的问题把剩下链表中的节点继续两两交换。也就是说原问题是“交换整个链表”子问题是“交换去掉前两个节点后的剩余链表”本质上还是同一种问题只是规模变小了。所以这道题适合用递归来做。第二步只写“当前层”的逻辑”我们不去想递归会展开多少层也不要急着想最后链表整体是怎么接起来的只需要考虑当前这一层该做什么。当前层只需要处理前两个节点先把后面剩余部分交给递归函数swapPairs(head-next-next)去完成递归返回的是“后面已经两两交换好的链表头”。然后当前层再把前两个节点交换过来也就是让第二个节点变成新的头结点让它指向第一个节点再让第一个节点接上后面已经处理好的链表。所以当前层逻辑就是交换当前这两个节点并把后面递归处理好的结果接回来。第三步写清楚出口递归一定要有结束条件。对于这道题来说如果链表为空那么自然没法交换直接返回空即可如果链表只剩下一个节点那么也没有成对的节点可以交换直接返回这个节点即可。所以递归出口就是当head nullptr或者head-next nullptr时直接返回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* swapPairs(ListNode* head) { if (head nullptr || head-next nullptr) return head; ListNode* tmp swapPairs(head-next-next); ListNode* next head-next;//当前层新头结点 //交换当前这两个节点并把后面递归处理好的结果接回来 head-next-next head; head-next tmp; return next; } };运行结果顺利通过~这一篇博客先到这里后面还会有新的递归练习博客我们下次见~♥♥♥本篇博客内容结束期待与各位优秀程序员交流有什么问题请私信♥♥♥♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥✨✨✨✨✨✨个人主页✨✨✨✨✨✨