一、同样的深度优先搜索，使用栈和使用递归的性能差别

同样的深度优先搜索，使用栈和使用递归的性能差别是，对于内存，栈的内容太多了。只压栈的话i和target应该够了，栈的内容只需要和DP的参数一样多。

递归

递归的基本思想是，把规模较大的一个问题，分解成规模较小的多个子问题去解决，而每一个子问题又可以继续拆分成多个更小的子问题。最重要的一点就是假设子问题已经解决了，现在要基于已经解决的子问题来解决当前问题；或者说，必须先解决子问题，再基于子问题来解决当前问题。

递归解决的是有依赖顺序关系的多个问题：假设一个抽象问题有两个时间点要素：开始处理，结束处理，那么递归处理的顺序就是，先开始处理的问题，最后才能结束处理。递归对问题的处理顺序，是遵循了先入后出（也就是先开始的问题最后结束）的规律。

深度优先搜索

深度优先搜索（DFS）是用于在树/图中遍历/搜索的另一种重要算法。也可以在更抽象的场景中使用。

正如树的遍历中所提到的，我们可以用 DFS 进行 前序遍历，中序遍历 和 后序遍历。在这三个遍历顺序中有一个共同的特性：除非我们到达最深的结点，否则我们永远不会回溯。

这也是 DFS 和 BFS 之间最大的区别，BFS永远不会深入探索，除非它已经在当前层级访问了所有结点。

延伸阅读：

二、回溯是什么

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。

回溯法是一个既带有系统性又带有跳跃性的搜索算法：

系统性：在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树；

跳跃性：算法搜索至解空间树的任一结点时，判断该结点为根的子树是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先点回溯，否则，进入该子树，继续深度优先的策略进行搜索。

上一篇

什么是完美散列（perfecthashing）?