CODEWITHSUNDEEP
javagraphstackdepth-first-search
Filip Kłosiewicz
Filip Kłosiewicz

Reputation: 1

Depth-First-Search (Stack or Recursion?)

For DFS, do you always have to use a Stack? After doing some research, I see some people implement recursion instead of Stack iteration, and it seems to yield the same result.

Is one more efficient than the other? Plenty of recursive algorithms employ a secondary or even sometimes tertiary helper methods that run recursively.

I'm asking as I have to employ DFS on a Graph, I've been trying to do recursion, I think I almost nailed it, but I'm being cautious for any errors.

Upvotes: 0

Views: 825

Answers (1)

Nicktar
Nicktar

Reputation: 5575

I think, recursion is the more readable way to do a depth-first-search since your code execution is following the very idea you're implementing. On the other hand, recursion has certain risks since it uses the call stack which is a part of memory separate from where a stack data structure would be stored and it's limited in size. If your search is to deep, you'll trigger StackOverflowErrors and a termintaed execution.

The depth limit is hard to tell because the amount of memory needed for each recursion step depends on the number and type of your recursive methods parameters and I think the size of the call stack varies betwenn different JVM vereions and vendors.

Upvotes: 1

Related Questions