《算法题讲解指南：递归，搜索与回溯算法--递归》--1.汉诺塔，2.合并两个有序链表
🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
前言
从本篇文章开始我们就要讲解很多人一开始学习就感到非常不解以及迷茫，不清楚代码到底怎么执行的算法：递归、搜索与回溯算法。也许不仅仅是这个算法，很多人在学习C语言第一次接触递归这个东西的时候可能就是学习的一知半解，有时候都不清楚递归的过程到底是什么样子的，当看到一个函数中存在调用自己的情况就自然感到无力和一种恐惧感。这其实是非常正常的，但本篇文章讲解的目的不仅仅是讲解两道递归算法题，更是能让大家从此打消对递归的恐惧感，当以后不管是看到递归还是写递归算法题都能有非常清晰的思路。
递归，搜索与回溯算法前置知识(极其重要)
以下是基于上面自己对递归的一种新的认知，希望能帮助大家用另一种眼光来看待递归：
看待递归最重要的点就是：我们一定要清楚这个要进行递归的函数的功能（作用）到底是什么？
这个是非常重要的，因为递归的本质就是：自己调用自己。不妨问问我们自己，之前我们所写的代码只要遇到一个函数被调用的时候，我们为什么要调用这个函数，不就是需要用这个函数的功能吗，比如要执行加法操作，我可以调用一个加法的函数，就是为了利用这个函数的功能。
那回到这里，我们以归并排序为例，为什么我们实现归并就需要用到递归，我们就以上面的角度来看待：首先我们就一定要清楚归并函数mergesort的功能就是：让一个无序数值变成有序。好，接下来我们就来模拟实现一下归并：首先我们要知道归并是通过一个中间点将数组分成两部分，然后左边和右边数组利用一个操作分别有序再通过一个辅助数组将两个数组合并成一个有序数组，也就完成了无序变成有序的操作。
到这里应该就有人对递归有了不一样的认知了，上面那个操作其实就是递归。为什么？就是我们最上面所讲的调用函数就是为了利用其功能：我们是利用一个什么操作才能让左边和右边数组分别有序呢？难道不就是用一下归并排序函数mergesort吗？因为这个函数的功能不就是将一个无序数组变成有序吗？那这里肯定就有人要问了：我们都还没实现完归并排序函数怎么就能用这个函数的功能？所以接下来我要讲的一个点就是（宏观的看待递归的过程）：不要去下意识在意函数调用自己的递归细节展开图（这也是一开始很多人学习递归的习惯），我们要抱着相信的态度去看待递归，虽然我们还没实现完函数，但是我们调用这个函数本身就是相信这个函数能帮助我们实现功能。
所以当写了mergesort（nums，left，mid）；这个操作就要心里有个底：此时左边的数组已经完成了排序，究竟具体怎么操作实现的一定不要去就纠结，我们就相信当调用这个函数后左边数组就能变成有序！然后再写mergesort（nums，mid+1，right）；这个操作也要知道此时右边的数组也已经完成了排序，也是不要去深挖其中的过程。
则两边数组此时已经完成了排序，接下来的操作就是利用一个辅助数组进行合并，这里就不细讲了。
当我们有上面对递归这种理解后就会发现，当我们以后写递归算法时就不会一直往递归的深度过程去想，也就是当我们看到一个地方使用递归了就又下意识重新回到函数开始来看问题，这非常容易把自己陷进去，所以上面对递归的一种本质理解能够让我们以后写递归不会产生畏惧感和纠结。
最后我们只需要注意一个细节问题就是：保证递归有结束，也就是说在函数开头要有一个递归结束的条件，这个就是看题论题了。
1.汉诺塔
题目链接：
面试题 08.06. 汉诺塔问题 - 力扣（LeetCode）
题目描述：
题目示例：
解法(递归)：
算法思路：
这是一道递归方法的经典题目，我们可以先从最简单的情况考虑：
假设 n=1，只有一个盘子，很简单，直接把它从A中拿出来，移到C上；
如果 n=2 呢？这时候我们就要借助B了，因为小盘子必须时刻都在大盘子上面，共需要3步(为了方便叙述，记A中的盘子从上到下为1号，2号)：
a.1号盘子放到B上；
b.2号盘子放到C上；
c.1号盘子放到C上。
至此，C中的盘子从上到下为1号，2号。
如果 n>2 呢？这是我们需要用到 n=2 时的策略，将 A 上面的两个盘子挪到 B 上，再将最大的盘子挪到 C 上，最后将 B 上的小盘子挪到 C 上就完成了所有步骤。例如 n=3 时如下图：
因为A中最后处理的是最大的盘子，所以在移动过程中不存在大盘子在小盘子上面的情况。
则本题可以被解释为：
1.对于规模为 n 的问题，我们需要将A柱上的 n 个盘子移动到 C 柱上。
2.规模为 n 的问题可以被拆分为规模为 n-1 的子问题：
a.将A柱上的上面 n-1 个盘子移动到 B 柱上。
b.将 A 柱上的最大盘子移动到 C 柱上，然后将 B 柱上的 n-1 个盘子移动到C柱上。
3.当问题的规模变为 n=1 时，即只有一个盘子时，我们可以直接将其从 A 柱移动到 C 柱。
需要注意的是，步骤 2.b 考虑的是总体问题中的子问题 b 情况。在处理子问题的子问题 b 时，我们应该将 A 柱中的最上面的盘子移动到 C 柱，然后再将 B 柱上的盘子移动到 C 柱。在处理总体问题的子问题 b 时，A 柱中的最大盘子仍然是最上面的盘子，因此这种做法是通用的。
C++算法代码：
class Solution { public: void hanota(vector<int>& A, vector<int>& B, vector<int>& C) { dfs(A, B, C, A.size()); } void dfs(vector<int>& x, vector<int>& y, vector<int>& z, int n) { if(n == 1) //递归结束条件：x柱中只有一个盘子，直接放到z柱即可 { z.push_back(x.back()); x.pop_back(); return; } //先将n-1个盘中利用z柱放到y柱上 dfs(x, z, y, n-1); //再将x柱中最底下的盘中放到z柱上 z.push_back(x.back()); x.pop_back(); //最后将y柱上n-1个盘子利用x柱放到z柱上 dfs(y, x, z, n-1); return; } };算法总结及流程解析：
2.合并两个有序链表
题目链接：
21. 合并两个有序链表 - 力扣（LeetCode）
题目描述：
题目示例：
解法(递归)：
算法思路：
1.递归函数的含义：交给你两个链表的头结点，你帮我把它们合并起来，并且返回合并后的头结点；
2.函数体：选择两个头结点中较小的结点作为最终合并后的头结点，然后将剩下的链表交给递归函数去处理;
3.递归出口：当某一个链表为空的时候，返回另外一个链表。
注意注意注意：链表的题一定要画图，搞清楚指针的操作！
C++算法代码：
/** * 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的头节点更小，则将list1->next和list2放入该函数中实现两个链表的合并 //合并后就变成有序的了，返回的结点再于list1头节点相连则完成了合并 //具体list1->next和list2放入函数后怎么合并成有序我不管 //我相信函数能帮我实现出来，这也就是宏观视角看待递归 list2->next = mergeTwoLists(list1, list2->next); return list2; } else { //同理list2的头节点更小也是如此 list1->next = mergeTwoLists(list1->next, list2); return list1; } } };算法总结及流程解析：
结束语
到此，1.汉诺塔，2.合并两个有序链表 这两道算法题就讲解完了。理解递归的关键在于 相信函数功能 的宏观视角，避免陷入递归展开细节。希望大家能有所收获！
