递归和深度优先搜索是否等效？

Question

我想知道是否可以将任何递归算法实现重新定义为DFS图遍历。

- Christian Leon

---

你可以使用堆栈来迭代实现深度优先搜索（DFS）。大多数实现都使用函数调用堆栈，因此递归作为一种替代方法。总的来说，递归并不是DFS。 - sve

Answer 1

我认为许多递归算法可以被视为深度优先搜索（DFS）。问题在于，你认为DFS操作的图是什么。

例如，如果你有一个如下类型的递归：

f(n1,...,nk)=G(f(n1',...nk'), f(n1'',...,nk''),...)

这段文字讲的是将递归关系转化为一个图，在这个图上进行深度优先搜索（DFS）和递推计算是等价的。举例说明了如何将斐波那契数列转化为这样的图，并解释了DFS使用记忆化技术，每个配置只计算一次，而不是像朴素的斐波那契数列实现需要反复计算的原因。同时，提到了一个反例，即对于某些函数，把其参数看成节点建立的图无法被转化为DFS形式。

- ead

Answer 2

不，这里有一个算法，你不会找到DFS遍历。

func A(graph):
   if graph is empty:
       stop
   print random vertex from a graph
   func A(grap without this vertex)

这显然是一个在图上的递归算法。尝试找到一个类似的深度优先搜索算法。

- Salvador Dali

---

那么，一般来说，有些递归算法可以重写为DFS的迭代版本，这是常识吗？ - Christian Leon

@ChristianLeon DFS 意味着你从一个元素移动到它的元素。递归意味着你通过自身来定义某些东西。递归比 DFS 更广泛。 - Salvador Dali