算法训练之递归（一)

---

♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥

♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥

♥♥♥我们一起努力成为更好的自己~♥♥♥

♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥

♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥

✨✨✨✨✨✨ 个人主页✨✨✨✨✨✨

---

小伙伴们，好久不见！今天这一篇博客，主要是递归算法的学习与练习~准备好了吗~我们发车去探索算法的奥秘啦~🚗🚗🚗🚗🚗🚗

目录

一、递归简单介绍

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-1

3.一定要有“出口”

没有出口，递归就会一直调用下去，最后栈溢出。所以递归一定包含两部分：递归体：把问题拆小，继续调用自己；递归出口：什么时候停下来，进行返回。

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; } };

运行结果：

顺利通过~

这一篇博客先到这里，后面还会有新的递归练习博客，我们下次见~

---

♥♥♥本篇博客内容结束，期待与各位优秀程序员交流，有什么问题请私信♥♥♥

♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥

✨✨✨✨✨✨个人主页✨✨✨✨✨✨

---