[r-t] Bobs only Erin Triples (was: Composition search)
ian at broster.co.uk
Wed Nov 25 14:00:54 UTC 2015
>> Obviously, an easy optimization is to do this in a loop rather than a
>> recursive call. That more than doubles the speed,
> I'm sorry, but that's utter bollocks. If your recursive implementation
> is twice as slow as a loop-based solution, you've done it wrong, or
> you're using a ridiculously high-level language. The cost of a function
> call is simply not that high.
I agree that the recursive/loop decision gains are almost irrelevant to
the tree pruning for a search space of this size.
Nevertheless for smaller problems, when I went from recursive to loop I
did get a significant improvement. I think that gains were probably
through better cache management (using a small data structure instead of a
the call stack) and being able to skip all the calls to leaves - you could
do this in a recursive structure by doing the base case before the call.
I doubt that my recursive version was great - once I'd written the
recursive version, I understood the problem enough to write a better
version 2 (which happened to be loop-based)!
More information about the ringing-theory