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

📝前言说明：

• 本专栏主要记录本人递归、搜索与回溯算法的学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行该专题内不同子专题的学习

暂时没有	暂时没有

一，名词解释

递归和搜素与回溯的关系是：递归包含搜索，搜索包含回溯

1， 递归

1.1 什么是递归

• 函数自己调用自己。

1.2 为什么会用到递归

• 以，二叉树的遍历，快排，归并为例：
• 解决主问题 → 遇到相同子问题
• 解决子问题 → 遇到相同子问题

1.3 如何理解递归

1.3.1 理解递归展开的细节图

以前序遍历为例：

1.3.2 利用部分基础二叉树题目来感受

因为二叉树本身就具有非常强的递归特性，这里给三道题目：

• 单值二叉树
• 相同的数
• 另一棵树的子树

1.3.3 宏观看待递归过程

当我们对递归有一定的感知以后，我们写递归题目的时候，不要过度关心细节，应该宏观看待递归过程
怎么宏观：

• 不要关系递归的细节展开图（不要题题都想着展开搞明白调用流程）
• 把递归函数当做一个黑盒子（我们只管用就行了）
• 相信这个黑盒子一定能返回我们要的结果

4. 如何写好一个递归

• 先找到相同的子问题 → 函数头的设计
• 只关心一个子问题是如何解决的 → 函数体的设计
• 子问题不能再分时 → 注意递归函数的出口（结束条件）

以后续遍历为例：

• 父问题：对对应根节点的树进行后续遍历。子问题：对子树也后续遍历 → 函数头（传入根节点）
• 子问题如何解决： 先访问左子树和右子树（我们相信递归函数一定能完成），然后再访问根节点printf
• 递归出口：当节点为NULL

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

1. 深度优先遍历 vs 深度优先搜索

• 前序遍历就是一种深度优先遍历（dfs），即：一条路走到头，不能再走了才返回去走其他路
• 深度优先搜索：本质和深度优先遍历一样，只是目的是搜索
• 关系：遍历是形式，目的是搜索

2. 广度优先遍历 vs 广度优先搜索

• 如层序遍历，就是广度优先遍历（bfs）
• 两者关系与 深度优先遍历 vs 深度优先搜索之间的关系一样

3. 暴搜

暴搜，即：暴力枚举一遍所有结果（如：dfs 和 bfs）

4 扩展搜索问题

除了与二叉树有关的问题，其他问题我们能否用递归呢？
下面以求1、2、3全排列的所有结果 举例：
我们把问题画成树状图：

上面就是一颗决策树，一样可以用dfs得到所有结果

三，回溯与剪枝

回溯：

• 回溯的本质就是深度搜索
• 在深搜过程中，发现一条路走到头了，进行回溯

剪枝：

• 发现一条路肯定是错的，没必要再走时，剪枝

红色部分就是回溯
剪枝：

• 如，橙色的①和②
• 先走了①，发现走不通于是回溯到分叉口位置，然后走②，发现也走不通，也回到分叉口位置
• 此时，可以选择往上走和往下走，但是①必然是不正确的选择（因为之前已经得出结论了），所以直接剪枝，不走上面

四，本专栏介绍

本专栏会有以下专题：

• 专题一：递归
• 专题二：二叉树的深搜
• 专题三：穷举 vs 暴搜 vs 深搜 vs 回溯 vs 剪枝
• 专题四：综合练习
• 专题五：FloodFill算法
• 专题六：记忆化搜索

---

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！