【递归，搜索与回溯算法篇】- 名词解释
一. 递归
1. 什么是递归？
- 定义： 函数自己调用自己的情况
- 关键点：
➀终止条件： 必须明确递归出口，避免无限递归
➁子问题拆分： 问题需能分解成结构相同的更小的子问题 - 缺点：
➀栈溢出风险： 递归深度过大时可能引发栈溢出
2. 为什么会用到递归？
- 二叉树的后序遍历
- 快排
- 归并
3. 如何理解递归？
- 递归展开的细节图
- 二叉树中的题目
- 宏观看待递归的过程
➀不要在意递归的细节展开图
➁把递归的函数当成一个黑盒
➂相信这个黑盒一定能完成任务
4. 如何写好一个递归？
- 先找到相同的子问题 -> 函数头的设计
- 只关心某一个子问题是如何解决的 -> 函数体的部分
- 注意递归函数的出口
手写笔记：
二.搜索 vs 深度优先遍历 vs深度优先搜索 vs 宽度优先遍历 vs 宽度优先搜索 vs 暴搜
- 深度优先遍历 vs 深度优先搜索 ->
dfs - 宽度优先遍历 vs 宽度优先搜索 ->
bfs
遍历是形式，目的是搜索
手写笔记：
3. 回溯与剪枝
回溯：
- 本质： 就是深搜
- 在找某种情况的时候，发现这个情况行不通，然后返回到上一级的操作
- 核心思想：
- 路径： 记录已做出的选择
- 选择列表： 当前可用的选项
- 结束条件： 满足条件时将路径加入结果
剪枝：
- 目标： 减少无效搜索，提前终止不可能到达解的路径
- 剪枝策略：
- 可行性剪枝： 当前路径明显不满足约束时终止
- 去重剪枝： 避免生成重复解
- 最优解剪枝： 在求最优解时，若当前路径已劣于已知最优解，提前终止