2 ms·
It 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 recursiv
by AstralStorm 9y ago
It 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?