0

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?

Luca
  • 10,458
  • 24
  • 107
  • 234
  • this is a pretty broad question. what language are you working with anyway? – Mulan Apr 21 '17 at 22:34
  • @naomik I understand so. I was just wondering what would for example a commercial software implement? I am using python. – Luca Apr 21 '17 at 22:35
  • 1
    Since you are using python, you should definitely use the iterative version, since the maximum recursive depth in python is quite small. You can use the function sys.getrecursionlimit() to see the actual limit, and change it with sys.setrecursionlimit(x) just in case you really want to use the recursive version – Lucas Sampaio Apr 21 '17 at 22:40
  • 1
    The recursive version is almost always easier to read/write; if your data is not significantly deep, a recursive version should be fine. – Mulan Apr 21 '17 at 22:41
  • [Recursion or while loops.](https://softwareengineering.stackexchange.com/questions/182314/recursion-or-while-loops) [Recursion versus iteration.](http://stackoverflow.com/questions/15688019/recursion-versus-iteration) – Bernhard Barker Apr 22 '17 at 00:56

1 Answers1

2

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.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
  • some languages are stack-safe even if recursion is used though, so this doesn't apply in all cases – Mulan Apr 22 '17 at 04:21