[r-t] Bobs only Erin Triples (was: Composition search)

[Ian Broster]

>> 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)!

i.



-- 
Ian Broster