I've tried to compare recursive tree DFS and iterative one (with stack in Python list) implemented in Python - recursive was slightly faster. I've not compared memory usage thought. Function call has overhead and theoretically recursive approach should be slower, but list manipulation (append, pop) in Python is also not fast. In compiled languages results can differ (iterative probably will be faster).
Yeah, that’s true. I would expect manual recursion in Python using append/pop on a list based stack to be slower than native recursion. You might try pre-allocating your entire stack in a list or numpy array, and not using append & pop during the recursion at all. I might expect that to be faster than native recursion.
