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

[Alan Burlison]

On 25/11/2015 14:00, Ian Broster wrote:

>>> 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.

That's very architecture-dependent, and will be affected by how much 
much local state needs to be saved on the stack. Plus a call stack 
that's very deep risks blowing the stack anyway - on *NIX systems it's 
commonly 8Mb by default, on Win I believe it's 1Mb. And of course stack 
limits are more of a problem if you are multithreaded as each thread 
gets it's own stack.

Many HLLs that make heavy use of recursion automatically convert 
recursion into iteration, but there are often restrictions in the way 
you write your code if that is to be possible. gcc will do TCO for C and 
C++ code if it can, but you usually need to look at the generated 
assembly to see if it has happened.

-- 
Alan Burlison
--