【递归，搜索与回溯算法篇】- 名词解释

一. 递归

1. 什么是递归？

• 定义： 函数自己调用自己的情况
• 关键点：
  ➀终止条件： 必须明确递归出口，避免无限递归
  ➁子问题拆分： 问题需能分解成结构相同的更小的子问题
• 缺点：
  ➀栈溢出风险： 递归深度过大时可能引发栈溢出

2. 为什么会用到递归？

• 二叉树的后序遍历
• 快排
• 归并

3. 如何理解递归？

1. 递归展开的细节图
2. 二叉树中的题目
3. 宏观看待递归的过程
   ➀不要在意递归的细节展开图
   ➁把递归的函数当成一个黑盒
   ➂相信这个黑盒一定能完成任务

4. 如何写好一个递归？

1. 先找到相同的子问题 -> 函数头的设计
2. 只关心某一个子问题是如何解决的 -> 函数体的部分
3. 注意递归函数的出口

手写笔记：

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

1. 深度优先遍历 vs 深度优先搜索 -> dfs
2. 宽度优先遍历 vs 宽度优先搜索 -> bfs
   遍历是形式，目的是搜索

手写笔记：

3. 回溯与剪枝

回溯：

1. 本质： 就是深搜

• 在找某种情况的时候，发现这个情况行不通，然后返回到上一级的操作

2. 核心思想：

• 路径： 记录已做出的选择
• 选择列表： 当前可用的选项
• 结束条件： 满足条件时将路径加入结果

剪枝：

1. 目标： 减少无效搜索，提前终止不可能到达解的路径
2. 剪枝策略：

• 可行性剪枝： 当前路径明显不满足约束时终止
• 去重剪枝： 避免生成重复解
• 最优解剪枝： 在求最优解时，若当前路径已劣于已知最优解，提前终止