4 ms·
If recursion could be tail-optimized, it's usually better just to write iterative `white`, unless you can't use mutable variables. The interesting recursion whi
by vbezhenar 9y ago
If 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?