【算法】递归、搜索与回溯

递归

什么是递归？

递归就是函数自己调用自己的情况

为什么会用到递归？

本质：

• 主问题→相同的子问题
• 子问题→相同的子问题

如何理解递归？

小白阶段：

• 先通过理解递归展开图进行理解递归是如何进行的

老鸟阶段：

• 不要在意递归的细节展开图
• 把递归的函数看成一个黑盒
• 相信这个黑盒一定可以完成这个任务（这种信任基于递归的细节展开图）

如何写好一个递归？

1. 先找到相同的子问题！！！→函数头的设计
2. 只关心某一个子问题是如何进行解决的 →函数体的设计
3. 注意一下递归函数的出口，防止出现死递归

递归和循环的关系

递归和循环都是解决重复子问题，也就是说循环和递归是可以进行相互转化的，但是递归的很多代码用循环进行实现是十分恶心的。

什么时候用循环舒服，什么时候用递归舒服？

递归的展开图本质上就是对一棵树进行一次深度优先遍历，深度优先遍历（DFS）过程中，我们始终要遵循 先深入，再回溯 的原则。递归调用时，系统会自动用栈来管理函数调用的返回地址和当前的执行状态，而如果我们改用循环，就必须自己手动管理这个「回溯」的过程，而 栈 恰好是符合 后进先出（LIFO） 逻辑的数据结构，非常适合模拟深度优先遍历。对于这种树的结构通过循环进行往往是很复杂的。

循环对处理那种单支的结构相对来说比较友好，例如下面这种遍历数组。

搜索vs深度优先遍历vs深度优先搜索vs宽度优先遍历vs宽度优先搜索vs暴搜

搜索与遍历的区别

深度优先遍历与深度优先搜索→dfs

宽度优先遍历与深度优先搜索→bfs

遍历只是形式，目的是搜索

关系图

搜索（暴搜）

• dfs
• bfs 

拓展搜索问题

以  1，2，3  全排列的问题举例

通过树状图的形式进行枚举

回溯与剪枝

回溯与剪枝的理解

通过迷宫的例子进行理解回溯与剪枝，我们需要从起点进行进入，然后走出终点，当路线进行撞墙后原路进行返回到存在多条路线的路口，继续进行选择另一条路， 回溯的本质就是深搜（不装南墙不回头）。通过额外条件避免不必要的尝试，就是剪枝，这个人如果知道某条路明显走不通（比如已经封死了），他就直接跳过，不去浪费时间尝试。

剪枝是回溯的优化

08.06汉诺塔问题

题解

概念明确

• 盘子分为最下面盘子和其他盘子
• 柱子分为起始柱、辅助柱和目标柱

例如当N=3时，刚开始需要将A柱最下面的那个盘子进行移动到C柱上，此时A是起始柱，C是目标柱、B是辅助柱，需要将其他盘子借助B进行将A柱上最大的盘子进行移动到C上，然后B就成了起始盘，A成了辅助盘，C还是目标盘，通过借助辅助盘将最大的盘进行移动到目标盘上。

代码思路

通过上面的举例可以进行将盘子进行看成两个部分，分别是最下面的那个盘子和其他盘子，首先借助辅助盘进行将最大的移动到目标盘，然后刚刚的起始盘和目标盘身份发生了互换，继续借助辅助盘进行将当前最大的移动到目标盘。

• 递归的主问题

将A上的所有盘子借助B转移到C上

• 递归的子问题

要想实现将A上的所有盘子借助B转移到C上，第一步需要将A上的n-1个盘子借助C转移到B上，然后将A上的最后一个盘子放到C上，第二步将B上的n-1个盘子借助A转移到C上即可。

• 递归的结束条件

当只剩最后一组时，盘子时进行手动处理一下即可

编写代码

class Solution {
public:void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {//主问题--将A上的盘子借助B转换到C上dfs(A,B,C,A.size());}void dfs(vector<int>& A, vector<int>& B, vector<int>& C,int num){//处理递归的结束条件if(num==1){C.push_back(A.back());A.pop_back();return;}//子问题//1.将A上的n-1个盘子借助C转移到B上    //将A上的最后一个盘子转移到C上dfs(A,C,B,num-1);C.push_back(A.back());A.pop_back();//2.将B上的盘子的所有盘子转移到C上dfs(B,A,C,num-1);}
};

进行理解递归展开图 

21、合并两个有序的链表 

采用递归的方式

首先进行考虑为什么可以使用递归进行解决这个问题？

递归的本质就是重复子问题，这道题是存在重复子问题的，我们把通过两个指针 l1 和 l2分别指向两个链表，谁小谁作为头结点，剩下的就是合并剩余的两个链表，这就是重复子问题

递归代码的书写思路

• 函数头的设计--- 重复子问题

需要进行传入两个链表的头结点，然后进行返回较小的那个节点

• 函数体的设计---只关心某一个子问题在做什么事情

首先进行判断链表的哪个节点小进行作为头节点

然后进行通过递归的方式将剩余的两个链表进行放入递归中，我们认为这个递归函数是一定能帮我进行解决完成这个问题。

• 递归的出口

当有一个链表为空时进行返回另一个链表

/*** 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(list1,list2->next);return list2;}}
};

采用循环的方式 

/*** 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) return list2;if (!list2) return list1;if(list1&&list2&&list1->val>list2->val){ListNode*temp=list1;list1=list2;list2=temp;}ListNode* newlist1=list1;ListNode* newlist2=list2;ListNode*prev1=nullptr;while(newlist1&&newlist2){ListNode* next1;ListNode* next2;if(newlist2->val<=newlist1->val){next2=newlist2->next;next1=newlist1->next;newlist2->next=newlist1;if(prev1==nullptr){list1=newlist2;}else{prev1->next=newlist2;}prev1=newlist2;newlist2=next2;}else{prev1=newlist1;newlist1=newlist1->next;}}if(newlist2!=nullptr){prev1->next=newlist2;  }return list1;}
};

206、反转链表 

采用循环的方式

class Solution {
public:ListNode* reverseList(ListNode* head) {if(head==nullptr){return nullptr;}ListNode* prev=nullptr;ListNode*cur=head;while(cur){ListNode*next=cur->next;cur->next=prev;prev=cur;cur=next;}return prev;}
};

采用递归的形式

通过两个视角进行看待问题

宏观角度

从整体上看，我们的目标是反转整个链表。要做到这一点，我们可以将问题拆解为一个更小的相同问题：

• 先假设除了头结点的部分都已经被反转好了；

• 然后，我们只需要处理头结点的指向，使其正确连接到反转后的链表末尾。

这就意味着：

• 子问题：反转头结点之后的部分（递归解决）

• 当前层的任务：调整头结点的指向，使其连接到新的反转链表（直接操作）

 函数头的设计--相同的子问题

我们进行输入需要进行反转的链表的头结点，然后进行返回一个进行反转好了的链表的头节点。

函数体的设计--只关心某一个子问题在做什么事情

我们认为将除了头结点的链表交给递归，我们相信递归一定可以完成这个反转。只需要我们进行处理当前层即可。

递归的结束条件

刚开始这个这个链表就是空链表时还有就是当链表只有一个节点时，直接返回 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* reverseList(ListNode* head) {if(head==nullptr||head->next==nullptr){return head;}ListNode* newhead=reverseList(head->next);head->next->next=head;head->next=nullptr;return newhead;}
};

 24、两两交换链表中的节点

采用递归的形式 

我们整体的目标是将整个链表中的节点进行两两交换，我们可以将问题进行拆解成一个更小的相同问题

先假设除了刚开始的两个节点其他都已经进行两两交换完毕了

然后进行处理当前的两个节点

这就意味着

子问题：除了刚开始的两个节点，反转剩余的链表中的两两节点

当前层：进行处理刚开始的两个节点，使其能正确连接在这个链表中

函数头的设计--相同子问题

将子链表的头结点进行传入，将进行两两节点进行反转的链表的头节点进行返回。

函数体的设计--只关心某一个子问题在做什么事情

将除了刚开始的两个节点的剩余链表进行传入，认为递归一定可以帮我们进行处理完毕。

递归的结束条件

刚开始的链表就是空时，还有就是进行两两反转只剩一个节点时，这已经就是反转完成的。

/*** 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*newNode=swapPairs(head->next->next);ListNode* ret=head->next;//进行处理当前层head->next->next=head;head->next=newNode;return ret;}
};

 50、Pow（x，n）

题解

将整个大问题进行拆解成小问题

函数头的设计--相同子问题 

输入我们要进行运算的数和需要进行多少次幂的运算

输出将数的幂运算结果进行返回

函数体的设计--只关心某一个子问题是如何进行解决问题的

我们认为将需要进行运算的整数和需要进行运算的幂的次数传给递归函数，函数一定可以将运算成功并将结果进行返回。

递归结束的条件

进行运算的幂的次数变成0时

细节处理

• n 可能是负数

如果是负数需要进行处转换成1/这个数的多少次幂次方

• n 可能是 -2^31

1/2^31就会出现溢出现象所以说需要进行将int 转成long long

class Solution {
public:double myPow(double x, int n) {return n<0?1.0/Pow(x,-(long long)n):Pow(x,n);}double Pow(double x,int n){if(n==0){return 1.0;}double ret=Pow(x,n/2);return n%2==0?ret*ret:ret*ret*x;}
};

2331、计算布尔二叉树的值 

题解

这道题其实就是二叉树的后续遍历

可以将整个问题（二叉树）进行转化成 左子树、根、右子树

函数头的设计--相同子问题

输入：将要进行处理的子树进行放入递归函数中

输出：将子树进行处理的结果进行输出

函数体的设计--只关心某一个子问题的是如何进行解决问题的

我们认为将子树进行丢给递归函数，递归函数一定会进行处理完成，并将结果进行返回给这颗子树的头结点

递归结束的条件

当这个子树是孩子节点是不在继续执行递归。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool evaluateTree(TreeNode* root) {//本质就是二叉树的后续遍历if(root->left==nullptr&&root->right==nullptr){return root->val==1?true:false;}bool left=evaluateTree(root->left);bool right=evaluateTree(root->right);return root->val==2?left|right:left&right;}
};

129、求根节点到叶子节点的数字之和 

二叉树的递归非常好写，只需要进行观察递归到某一层是需要干什么事情

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int sumNumbers(TreeNode* root) {return dfs(root,0);}int dfs(TreeNode* root,int presum){presum=presum*10+root->val;if(root->left==nullptr&&root->right==nullptr){return presum;}int ret=0;if(root->left){ret+=dfs(root->left,presum);}if(root->right){ret+=dfs(root->right,presum);}return ret;}
};