辨析DFS 、回溯法和递归

本来题目叫做 Backtracking 回溯法总结的，搜了一圈发现好多既然连 DFS 、回溯法和递归之间的区别都傻傻分不清，所以也把内容重新组织下。

我的新书《LangChain编程从入门到实践》 已经开售！推荐正在学习AI应用开发的朋友购买阅读！

回溯法

• 回溯是一种通用的算法思想，把问题分步解决，在每一步都试验所有的可能（回溯本质上是一种穷举。），当发现已经找到一种方式或者目前这种方式不可能是结果的时候，退回上一步继续尝试其他可能。当每一步的处理都是一致的，这时候用递归来实现就很自然。

  识别回溯

• 判断回溯很简单，拿到一个问题，你感觉如果不穷举一下就没法知道答案，那就可以开始回溯了。
• 一般回溯的问题有三种：
  • Find a path to success 有没有解
  • Find all paths to success 求所有解
    • 求所有解的个数
    • 求所有解的具体信息
  • Find the best path to success 求最优解

    解决模板

• 关于回溯的三种问题，模板略有不同，
  • 第一种，返回值是true/false。
  • 第二种，求个数，设全局counter，返回值是void；求所有解信息，设result，返回值void。
  • 第三种，设个全局变量best，返回值是void。

    八皇后问题

• 给个n，有几种解；Leetcode N-Queens II
• 给个n，给出所有解；Leetcode N-Queens I

  递归

• 递归算法是一种直接或者间接调用自身函数或者方法的算法。有如下三个特点：
  1. 一个问题的解可以分解为几个子问题的解
  2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
  3. 存在递归终止条件，即必须有一个明确的递归结束条件，称之为递归出口

     解决模板

• 总结一下如何写递归代码：
  1. 找到如何将大问题分解为小问题的规律
  2. 通过规律写出递推公式
  3. 通过递归公式的临界点推敲出终止条件
  4. 将递推公式和终止条件翻译成代码

     相关问题

• 爬楼梯
• 划分为k个相等的子集

  DFS

• 深度优先搜索（DFS）算法，即是一种搜索算法。他的特点是在搜索时会面临多个选择，当选择某一个情况后仍然会面临多个选择。那么，他每一次都选择一个情况时，会继续沿着这个“方向”搜索下去，直到遇到边界无法在搜索时，结束当前分支路径的搜索。接着，进行其他路径的搜索。以这种方式持续下去，直到将所有的路径搜索完毕。经典的案例，比如对于BST（二叉搜索树）的先序遍历、中序遍历和后序遍历。
• 回溯搜索是深度优先搜索（DFS）的一种，对于某一个搜索树来说（搜索树是起记录路径和状态判断的作用）。其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。在深度优先搜索中，用标志的方法记录访问过的状态，这种处理方法使得深度优先搜索法与回溯法没什么区别了。

  参考链接

• Backtracking回溯法(又称DFS,递归)全解
• 看动画轻松理解「递归」与「动态规划」