algorithm - 递归和 DFS 等价吗？

Question

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

Answer 1

我认为您可以将许多递归算法视为 DFS。问题是，您认为 DFS 在其上运行的图是什么。

例如，如果您有类型的重复

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

图表应该是什么？如果您将配置 (n1,...,nk) 理解为图的顶点，并表示配置 (n1,...nk) 的依赖关系配置 (n1',...,nk'), (n1'',..., nk''), ... 作为这些顶点之间的有向边，递归的计算和该图上的 DFS 将是等效的。

例如，对于斐波那契数列 f(n)=f(n-1)+f(n-2)，f(n) 将仅取决于一个参数(所以我为 n1 写了 n)。 G 操作将是总和:G(f(n-1), f(n-2)):=f(n-1)+f(n-2)

在新兴的抽象图中，顶点为 {0,1,2,3,4,...}，边为 {(2,0), ( 2,1), (3,1), (3,2), ...}。

DFS 使用内存并仅计算一次配置的值。并非每个循环都如此(经典示例是斐波那契数的简单实现)，但是每个循环都可以扩展为使用内存。

至于 Salvador 的反例，那么如果我们将函数 A 的参数理解为一个顶点(尽管被称为“图形”!)，那么 A 可以被视为作为 DFS(非常无聊，因为每个节点只有一个出边，即使是随机的)。

我知道，我的回答没有证据，但我希望你能明白为什么可以将复发视为 DFS。