1

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.

Community
  • 1
  • 1
FuzzyBunnySlippers
  • 3,387
  • 2
  • 18
  • 28
  • Please link the question you refer to. But in general if your depth is not small than explicit stack is usually better. – zch Dec 10 '13 at 14:14
  • @NonlinearIdeas both recursive or non recursive will have similar space complexity and stack overhead does not matter in case of backtracking as more often width of the recursion tree in most problems is very high as compared to depth – Vikram Bhat Dec 10 '13 at 14:16
  • @NonlinearIdeas I would suggest recursive backtracking because it is easy to code & debug. – Vikram Bhat Dec 10 '13 at 14:19
  • @zch - Apologies...had it in copy/paste buffer but forgot to put in...not enough coffee yet ;). I have linked it. – FuzzyBunnySlippers Dec 10 '13 at 14:54

1 Answers1

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.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351
  • I would think the compiled code size would be small enough to stay within the size of modern caches so code does not have to be swapped in/out to external memory. The iPhone 4S has an L1 cache of 32kb, L2 of 1M. That's for a handheld device, with desktops even larger. I agree the code will look cleaner and be shorter using recursion; I'm still curious about overall memory efficiency, however. – FuzzyBunnySlippers Dec 13 '13 at 12:37
  • @NonlinearIdeas: "Overall memory efficiency" is very nearly a wash. If you use recursion, then the implicit stack uses only the memory it needs. Granted, there might be some overhead for return addresses. If you use an explicit stack, then you need to allocate the stack to the largest size you might need, or use a stack that grows dynamically. Either of those two is going to waste memory. Add to that, the process's stack is *already reserved*, so if you use an explicit stack you're using more memory than if you use recursion. There are many variables to think about here . . . – Jim Mischel Dec 13 '13 at 22:19
  • Yeah..the more I thought about the question the more I realized that modern computers make it very hard to make a simple definitive answer here. It's probably better to go with ease of implementation and only worry about the "how can can I shave off" questions if the memory/speed metrics start to plummet. Good food for thought. Thanks for the feedback. – FuzzyBunnySlippers Dec 13 '13 at 22:36