4 ms·
The two biggest problems with recursion in practical use is that not all compilers can properly handle optimizations around tail calls, and not all TCO capable
by falcolas 9y ago
The two biggest problems with recursion in practical use is that not all compilers can properly handle optimizations around tail calls, and not all TCO capable compilers can handle all tail call cases.
If either case occurs, you run into the issue where you will seemingly randomly blow out your stack space when your list is too long, or your tree too deep. Then you have to fall back to a non-functional idiom (or do some other magical incantations to avoid function stacks, like Clojure's `loop` special form).
I think recursion is a great tool, but it's so poorly implemented in so many languages that it's simply too dangerous to use.
- vbezhenar 9y agoIf recursion could be tail-optimized, it's usually better just to write iterative `white`, unless you can't use mutable variables. The interesting recursion which can't be trivially replaced with loop is not tail optimizable.
- eru 9y agoYou can implement state machines as a set of mutually-recursive functions with one state = one function. Works very well, is tail-recursive and not trivially replaced by loops.
- AstralStorm 9y agoIt is quite replaceable if you represent the actual graph as a data structure with terminator nodes. No need for more recursion - the data structure is recursive, but algorithm is not. It is even easier to prove bounds. You get to prove correctness for cycles (if applicable), connectedness of the graph and whether a terminator node is connected to all acyclic arcs. (Latter can be a trivial proof on the constructor.) Just like for recursive implementation except proving the cycle lemmas is easier.
- eru 9y agoInteresting. In the implementation as function you trivially can give different states differently typed arguments. How do you do that in the version you sketch?
- setzer22 9y agoIn clojure you can always write a macro that will define your recursive function in an implicit loop form, if writing "loop" looks bad. That (or plainly using loop) forces you to be explicit whenever you want to use tail recursion (still unsure whether this is good or bad). But the good news is that now the compiler will catch as an error whenever you intended to use tail recursion and your function wasn't tail-recursive, which I'm sure has caused more than a headache in other recursion-heavy languages.