3 ms·
Simple answer: never unless you happen to have unbounded call stack depth. Stack sizes are limited on all architectures I'm aware of, on some even drastically.
by AstralStorm 9y ago
Simple answer: never unless you happen to have unbounded call stack depth.
Stack sizes are limited on all architectures I'm aware of, on some even drastically. And stack overflows are very tricky to handle correctly.
Unless you want to limit recursion depth manually or have proven that overflow cannot happen with a formal proof. (With your bounded stack size.)
In all other cases, explicit data structure (not necessarily a stack) will both make debugging easier and additionally uncover performance problems you haven't thought about.
- unclebucknasty 9y agoWell, I wasn't offering an opinion as to when recursion should be used--merely pointing out that the GP's proposed change didn't hold the same meaning as the original. >never unless you happen to have unbounded call stack depth. But, since you mention it, I'd have to disagree with your assertion. It's not just about call stack-depth or artificial limitations. There are plenty of use-cases wherein the search-space-depth itself is naturally bound, but unknown/variable down any particular path (e.g. category hierarchies). And, yes, we can impose reasonable "manual" limitations on still more use-cases to expand this universe even further. Using recursion in these cases is far more elegant than nested loops.
- AstralStorm 9y agoThat falls under "proved it cannot happen with a formal proof". If you didn't actually prove it you're playing with fire. Funny thing is that proofs over recursive functions are either very easy or terribly involved. Also it is a false dichotomy. Nested loops are not the only option.
- imtringued 9y agoAll physical machines have limited memory and therefore limited stack and heap sizes. Getting a stackoverflow or running out of memory are the same thing. So going from the stack to the heap doesn't mean you don't have to formally verify it.