[r-t] Bobs only Erin Triples (was: Composition search)
alan.burlison at gmail.com
Wed Nov 25 15:04:27 UTC 2015
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.
More information about the ringing-theory