递归与回溯有什么区别？怎么区分？
来源：8-2 什么是回溯
shanmufeng
2017-08-05
我看到一个博客说：回溯一般借用递归来实现。回溯就是让计算机自动的去搜索，碰到符合的情况就结束或者保存起来，在一条路径上走到尽头也不能找出解，就回到原来的岔路口，选择一条以前没有走过的路继续探测，直到找到解或者走完所有路径为止。就这一点，回溯和所谓的DFS（深度优先搜索）是一样的。
我想听听老师您的理解^_^
1回答
-
递归只是一种程序逻辑建立的机制：自己调用自己。和循环的概念类似，是一种组成逻辑的方式。
回溯是一种算法思想，本质其实是在树形的结构中进行“穷举”。二叉树的遍历是最好的解释回溯的方式：
1 / \ 2 3 / \ / \ 4 5 6 7
比如上面的二叉树，我们做前序遍历，先遍历了1->2->4这个路径，之后为了遍历其他的可能，我们要从4“回到”2，之后遍历5；然后我们再“回到”2，发现在2上也没有其他路径了，又“回到”1，然后去3继续遍历。可以看到，回溯的关键是“回来”继续寻找其他的可能。
我要没记错，在这一章讲回溯的时候，应该每一个问题我都相应的画了一棵回溯树，来展示对于每一个问题，寻找解的过程是怎样的。
但递归不是一种算法思想，所以我们通常说这个问题可以使用回溯法解决，具体实现可以使用递归实现。
可以回忆一下在二叉搜索树中插入节点，或者删除节点，我们可以使用递归实现，但这个过程不是在树中进行“穷举”，通常不叫回溯法。再比如，为链表插入一个节点，删除一个节点，翻转链表，这些任务都可以使用递归实现，但通常不叫“回溯”，因为不是在一个树形结构中做搜索。
更复杂一些，在后面讲解动态规划的时候，对于每一个问题，我都会讲解一个“记忆化搜索”的解法，这种解法和回溯很像，但并没有穷举整棵递归树，所以通常也不叫“回溯”。
不过，其实，对于这种概念，通常也不用较真。比如在面试时，你说：我使用回溯法，加上了记忆化的策略，具体是如何balabalabla... 大家也能听懂你的意思，不会有人较真，问你，到底什么是回溯？你这样做真的叫回溯吗？等等等等。我还没听说过有人因为不能明确阐释“回溯”的概念而被拒。懂不懂回溯，随便拿一个“经典”回溯问题问一下便知：）
所以，如果要想深入理解这个概念，如果基于这个课程的话，我的建议是：把七八九三章看完，将其中的例题和练习题都自己亲自实践一遍，然后再回过头用自己的感悟总结一下：什么是回溯，什么动态规划，什么是递归实现。到那时，相信你会有更多的体会：）
加油！
1412017-08-08
相似问题
回答 1
回答 1
回答 1
回答 1
回答 2