[plt-scheme] List loop timing

On Fri, Feb 15, 2008 at 12:43 PM, Prabhakar Ragde <plragde at uwaterloo.ca> wrote:
> Carl Eastlund wrote:
>
>  > What non-tail-recursive version of reverse are you comparing here?  It
>  > can be written non-tail-recursively and still have the same asymptotic
>  > complexity, and quite possibly the same or similar running time.
>
>  I'm thinking of naive structural recursion. This is one of the examples
>  I use to motivate tail recursion in first term (details of stack and
>  heap optimization are deferred to second term), though I am careful to
>  make Matthias's point that one does not always save time this way. --PR

To my knowledge, the naive structurally-recursive reverse uses append,
and is thus quadratic.  It's the removal of append, not of non-tail
recursion, that speeds it up.  This example shows that tail recursion
may hint at a fast implementation... but it's not the fast part
itself.  I could write the accumulator-reverse, the normally tail
recursive one, and defeat the tail recursion with an assertion after
the fact, and probably still get results almost as fast as the
tail-recursive version.

-- 
Carl Eastlund