Is classical (recursion based) depth first search more memory efficient than stack based DFS?

Question

I was looking at the responses to this question by @AndreyT and I had a question regarding the memory efficiency of classical DFS vs. stack based DFS. The argument is that the classical backtracking DFS cannot be created from BFS by a simple stack-to-queue replacement. In doing the BFS to DFS by stack-to-queue replacement, you lose the space efficiency of classical DFS. Not being a search algorithm expert (though I am reading up on it) I'm going to assume this is just "true" and go with it.

However, my question is really about overall memory efficiency. While a recursive solution does have a certain code efficiency (I can do a lot more with a few lines of recursive search code) and elegance, doesn't it have a memory (and possibly performance) "hit" because of the fact it is recursive?

Every time you recurse into the function, it pushes local data onto the stack, the return address of the function, and whatever else the compiler thought was necessary to maintain state on return, etc. This can add up quickly. It also has to make a function call for each recursion, which eats up some ops as well (maybe minor...or maybe it breaks branching predictability forcing a flush of the pipeline...not an expert here...feel free to chime in).

I think I want to stick to simple recursion for now and not get into "alternative forms" like tail-recursion for the answer to this question. At least for now.

Answer 1

Whereas you can probably do better than a compiler by explicitly managing a stack, the reward often isn't worth the extra work. Compilers are a lot smarter these days than a lot of people think. They're also not quite as good as others think sometimes--you take the good with the bad.

That said, most compilers can detect and remove tail recursion. Some can convert simple recursive functions to iterative solutions, and some really good compilers can figure out that local variables can be re-used.

Recursive solutions often result in smaller code, which means it's more likely that the code will fit into the CPU cache. A non-recursive solution that requires an explicitly managed stack can result in larger code, more cache misses, and slower performance than the "slow" recursive solution.

Finally, many solutions are most intuitively implemented recursively, and those solutions tend to be short and easy to understand. Converting a recursive solution to an iterative solution that involves explicitly managing a stack results in more lines of code that is often obscure, fragile, and difficult to prove correct.

I've found that an easy to code and understand recursive solution is usually plenty fast enough and doesn't use too much memory. In the rare case that profiling reveals my recursive implementation is the bottleneck (usually it's a comparison function or something similar that the recursive function calls), I'll consider a non-recursive solution. I don't very often realize a significant gain by making the change.