目录
题目一：汉诺塔问题
在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。
示例1:
输入：A = [2, 1, 0], B = [], C = [] 输出：C = [2, 1, 0]
示例2:
输入：A = [1, 0], B = [], C = [] 输出：C = [1, 0]
提示:
- A中盘子的数目不大于14个。
汉诺塔问题算是递归中的典型例题了，要求将A上的盘子挪到C上，在挪动过程中，只允许叠在比它大的盘子上
下面举个例子，刚开始是这样，先将小盘子挪到C上：
再将中间的盘子挪到B上，然后将C上的盘子挪到B上：
将A的大盘子挪到C上，再将B上面的小盘子挪到A上：
最后将B的盘子挪到C上，再将A的盘子挪到C上：
至此就成功将A上的盘子，借助B，挪到C上，且符合题目挪动的要求，上述就是汉诺塔问题挪动的过程
我们首先要明确一个目标，因为小盘子需要放到大盘子上面，所以挪动的首要目标就是将A中最底下的盘子挪到C上，接着挪动过程就需要借助辅助盘子B了
相当于将A上除了最大盘子外的其他盘子，挪到B这个辅助盘子上面，再将A的最大盘子挪到C上，最后将B上的盘子挪到C上
下面画图表示这个流程：
上图中 N = 1 和 N = 2 的情况不需要解释，当 N = 3 时，为了将A中最大的盘子挪动到C上，第一步就是将最大盘子上的其他盘子挪动到B上， 再将大盘子挪动到C上
而将大盘子上的两个盘子，通过借助C盘子挪动到B上，与 N = 2 的情况是完全一样的，只不过辅助盘子不同罢了，那么借助这个规律，N = 4也是一样的了：
为了将A的最大盘子挪到C上，第一步就是将A上面的3个盘子挪到B上，这一步就与 N = 3 的行为是一样的了
所以我们在解决N = 4时，出现了解决N = 3的情况，同样在解决 N = 3 时，出现了解决N = 2的情况，也就是：
大问题 -> 相同类型的子问题
子问题 -> 相同类型的子问题
编写递归的代码，有以下几步：
①重复子问题(函数头)
②只关心某一个子问题在做什么(函数体)
③递归的出口
先看第一步：重复子问题
在上述的过程中，每次都需要将一个柱子上一定数量的盘子，借助另一个柱子的帮助，挪动到第三个柱子上
即：将a柱子上的盘子，借助b柱子，转移到c柱子上
所以函数头为：void dfs(a, b, c, int n)
函数头上a、b、c柱子的顺序是有规律的，也就是与上面的话一一对应，n表示需要转移的盘子数量
第二步：只关心某一个子问题在做什么
如上面的图所示，某一子问题都是分为三步：
①先将a上的 n - 1个盘子借助 c 挪到 b
②将 a 上最大盘子挪到 c
③将 b 上所有盘子借助 a 挪到 c
所以函数体为(伪代码)：
dfs(a, c, b, n - 1);
a.back() -> c; a.pop_back();
dfs(b, a, c, n - 1);
第三步：递归的出口
通过上面的图可以看出，只有 N = 1 的情况不同，直接将 a 的盘子挪到 c 上，不借助辅助柱子
if(n == 1) a.back() -> c;
代码如下：
class Solution {
public:
void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n)
{
//递归的出口
if(n == 1)
{
c.push_back(a.back());
a.pop_back();
return;
}
// a 的 n-1 个盘子借助 c 挪到 b 上
dfs(a, c, b, n - 1); //第一步
c.push_back(a.back());//第二步
a.pop_back();
dfs(b, a, c, n - 1); //第三步
}
void hanota(vector<int>& a, vector<int>& b, vector<int>& c)
{
// a 的 n 个盘子借助 b 挪到 c 上
dfs(a, b, c, a.size());
}
};题目二：合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
这道题是非常熟悉的，在链表中是完成过这道题目的，当时是尾插到新链表的方式解决此题，而这里是使用递归的方式来解决的
使用递归解决，首先就需要找到重复子问题
刚开始合并题目给的两个链表，首先需要找两个链表中较小的那个结点做新链表的头结点，而挑选出该结点作为头结点后，就需要继续合并删掉该结点后的链表以及另一个链表，这里就找到了重复子问题了
1、重复子问题(函数头的设计)
通过上面的叙述，可以发现，这道题的重复子问题就是合并两个有序链表
Node* dfs(Node* l1, Node* l2);
2、只关心某个子问题在做什么(函数体的设计)
①比两个链表中第一个结点的大小
②假设l1小，此时 l1->next = dfs(l1->next, l2);
③return l1;
3、递归的出口(边界情况)
递归出口就是两个链表谁为空，就返回另一个链表即可
代码如下：
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当头结点，接收下面的这两个链表合并后的结果
list1->next = mergeTwoLists(list1->next, list2);
// 合并后返回头结点即可
return list1;
}
else// 同理
{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};题目三：反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
反转链表我们同样使用循环的方式写过，这里采用递归的方式再解决一下，有两种视角：
第一种视角：从宏观的视角看待
想要将链表逆序，那么只需要将第一个结点后面的链表逆置，此时再将第一个节点也放入这个逆置链表中
同样的，想要将第一个结点后面的链表逆置，只需要将后面这个链表的第一个结点，它后面的链表逆置，再将这个结点节点也放入这个逆置链表中
第二种视角：将链表看成一棵树
相当于一个树，每个结点只有一个孩子，一直向下，我们要做的就是相当于后面遍历，找到最后一个节点后，将该结点作为逆置链表的头结点，后再找上面的结点，进行指针翻转，并将上面的结点的指针指向空
这两种视角的代码是完全相同的，都是每次将下面的链表逆置后，将该结点也放入这个逆置链表中，也就是改变逆置链表最后一个节点与该结点的指针指向
代码如下：
class Solution
{
public:
ListNode* reverseList(ListNode* head)
{
// 如果没有节点或是只有一个结点，直接return head
if(head == nullptr || head->next == nullptr) return head;
// 先逆置第一节点后面的链表
ListNode* newhead = reverseList(head->next);
// 逆置完成后，再将第一个节点也放入这个逆置链表中，即改变指针指向
head->next->next = head;
head->next = nullptr;
return newhead;
}
};题目四：两两交换链表中的结点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输入：head = [] 输出：[]
示例 3：
输入：head = [1] 输出：[1]
同样采用宏观角度看待：
和上一题一样的思想，想要两两交换，只需要现将前两个结点后面的链表两两交换，再将前两个结点交换后，与后面交换成功的链表链接起来即可
而后面的链表与上述思想一样，都是这样解决的
代码如下：
class Solution
{
public:
ListNode* swapPairs(ListNode* head)
{
// 如果只有一个结点或是空节点，直接返回即可
if(head == nullptr || head->next == nullptr) return head;
// 将前两个结点的后面的链表先两两交换，交换后的链表的头结点返回给tmp
ListNode* tmp = swapPairs(head->next->next);
// 将前两个结点交换后，插入后面的链表中
ListNode* newhead = head->next;
head->next->next = head;
head->next = tmp;
// 最终返回前两个结点中的第二个结点，也就是上面记录的newhead结点
return newhead;
}
};题目五：Pow(x,n)
实现 pow(x, n)，即计算 x 的整数 n 次幂函数（即，x^n ）。
示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3 输出：9.26100
示例 3：
输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25
解法一：暴力解法
这个快速幂的题目，最先想到的肯定是暴力解法了，假设求 2^6，那就循环6次，每次都乘2，最终得到结果，但是如果次方数非常大，那就肯定会超时，所以就不考虑这种解法了
解法二：快速幂
快速幂也就是假设要求 2^6，那我只需要知道 2^3 即可，这样就可以直接 2^3 * 2^3 得到 2^6
同样 2^3 只需要知道 2^1 * 2^1 * 2，因为次方数3不能整除，所以这里再多乘一个2即可
同样想知道 2^1，只需要 2^0 * 2 就能得到，最终结束
快速幂的时间复杂度是：O(logN)
我们可以发现，上述的描述，每次求一个值时，都是相同的逻辑，也就是都是相同的子问题，此时就可以使用递归的方式了
所以只需：
1、重复子问题(函数头的设计)
int pow(x, n);
2、只关心某个子问题在做什么(函数体的设计)
tmp = pow(x, n/2);
return n%2 == 0 ? tmp * tmp : tmp * tmp * x;
3、递归的出口(边界情况)
n == 0 时return 1即可
有几个细节问题：
细节一：平方 n 有可能是负数
此时先将 n 看做正数，再用 1 除这个结果即可
细节二：n 可能是 - 2^31
如果 n 是 -2^31，此时将 n 转化为 2^31 会溢出，因为 int 类型存不下这个数据，int 类型最大值是 2^31 - 1，所以本题中我们需要将 n 的类型设置为 long long
代码如下：
class Solution
{
public:
double myPow(double x, int n)
{
// 处理n为负数的细节问题
return n < 0 ? 1 / pow(x, -(long long)n) : pow(x, n);
}
// n如果为负数，-n可能会溢出，所以这里改为long long类型的数据
double pow(double x, long long n)
{
if(n == 0) return 1.0;
double tmp = pow(x, n / 2);
return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
}
};[递归/搜索/回溯]系列之递归题目到此结束啦
![<span style='color:red;'>算法</span>专题[<span style='color:red;'>递</span><span style='color:red;'>归</span>-<span style='color:red;'>搜索</span>-<span style='color:red;'>回溯</span>-1]](https://img-blog.csdnimg.cn/direct/41ef801f08ac46a79f506bfca2b3cf8d.png)
