CODEWITHSUNDEEP
algorithmrecursiondepth-first-search
Luca
Luca

Reputation: 10996

depth first search recursive or iterative

I am studying depth first search and he recursive version is really simple to implement. With a slightly more complicated implementation, one can use a stack to implement a non-recursive version.

What are the pros and cons of the recursive vs the non-recursive version? In my simple test cases, I could not see any statistically significant timing differences.

One issue that I can think of is that the recursive case could end up with a stack overflow error. So is there any reason to use the recursive implementation at all?

Upvotes: 0

Views: 2252

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59154

You see a lot of recursive DFS in school, but in the real life business of writing software, you should never use recursion unless you know that it will be limited to a reasonable depth.

Generally that means that the depth is limited to O(log N), for example recursive DFS is fine in a balanced tree, or you know from the problem domain that very deep recursion won't happen, for example recursing into nested levels of syntax in recursive descent parsing.

A stack overflow is a catastrophic error, so if you don't know for sure that the depth is limited, then you should do the (little, really) extra work and write the iterative version with the stack on the heap.

Upvotes: 2

Related Questions