[plt-scheme] List loop timing

On Fri, Feb 15, 2008 at 2:05 PM, Prabhakar Ragde <plragde at uwaterloo.ca> wrote:
> Carl Eastlund wrote:
>  > My point is that removing append is what did something for
>  > its time, and tail recursion was serendipitous.  The saved time is all
>  > due to traversal of the list structure, and not due to the stack.
>
>  Most (not all) of the saved time is due to avoiding excessive list
>  traversal. But without working through the idea of using tail recursion,
>  one wouldn't have saved that time. If you insist on measuring the
>  savings due to tail recursion as the difference between the
>  tail-recursive function and the tail-recursive function spiked by
>  putting a trivial operation after each tail call, then, yes, the
>  difference is likely negligible. --PR

I don't insist on measuring a contrived function.  But if you want to
measure the savings of X, you can't trust comparisons that vary in
both X and Y.  For reverse, it happens that the only way to vary in
tail recursion but not list traversal is to use a contrived function;
that's incidental.

Personally, I learned how to write linear-time reverse in a lesson on
accumulators, in which tail recursion wasn't once mentioned (mostly
because I was programming in C).  You're used to seeing it tied up
with tail recursion, but the tie is not inherent.

-- 
Carl Eastlund