DFS Recursive vs DFS Iterative

Question

I'm trying to understand the difference between DFS Recursive and DFS iterative. Does the one with the stack use an iterative or recursive approach?

For example, what would be the output of using a DFS recursive traversal of the graph and a DFS iterative traversal of the graph? The neighbors are iterated through in alphabetical order.

Heres the graph:

For a DFS traversal (the one with a stack, not sure if its recursive or iterative) this is what I got: A, C, D, E, F. Can someone confirm what type of DFS traversal this is, and how the other one would work? Thanks!

Solution

To my understanding, the recursive and iterative version differ only in the usage of the stack. The recursive version uses the call stack while the iterative version performs exactly the same steps, but uses a user-defined stack instead of the call stack. There is no difference in the sequence of steps itself (if suitable tie-breaking rules are used to ensure equal traversal sequence for child nodes - if desired), so it is impossible to inspect the output to decide whether an iterative or recursive implementation was used.

Comments

[amit]

This is not entirely true. There are differences in the output between recursive and iterative approaches. See Iterative DFS vs Recursive DFS and different elements order for details

[Codor]

Well you are right, however as mentioned in the linked question, per se the order in which children are traversed is not specified; some additional order would have to be defined. I will change my answer a bit.