Are recursion and DFS equivalent?

I am wondering if any recursive algorithm implementation could be redefined as a DFS graph traversing.

2 Answers

I think you could consider a lot of recursive algorithms to be a DFS. The question is, what you consider to be the graph on which the DFS operates.

For example, if you have a recurrence of type

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

What should be the graph? If you understand the configurations (n1,...,nk) as vertices of the graph and express the dependency of the configuration (n1,...nk) from the configurations (n1',...,nk'), (n1'',..., nk''), ... as directed edges between these vertices, than the calculation of the recurrence and the DFS on this graph would be equivalent.

For example, for Fibonacci numbers f(n)=f(n-1)+f(n-2), f(n) would depend only on one argument (so I write n for n1). The operation G would be the sum: G(f(n-1), f(n-2)):=f(n-1)+f(n-2)

In the emerging abstract graph, the vertices would be {0,1,2,3,4,...} and edges would be {(2,0), (2,1), (3,1), (3,2), ...}.

DFS uses memoization and calculates the value for a configuration only once. It is not true for every recurrence (the classical example is the naive implementation of the Fibonacci numbers), however every recurrence can be extended to use memoization.

As for Salvador's counterexample, so if we understand the parameter of the function A as a vertex (despite being called "graph"!), than A can be viewed as DFS (pretty boring one, because every node has exactly one outgoing edge, even though random).

I know, my answer is no proof, but I hope you can get the idea why a recurrence can be seen as a DFS.

No, here is an algorithm for which you will not find a DFS traversing.

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

This is clearly some recursive algorithm on a graph. Try to find a DFS which will do something similar.