[plt-scheme] List loop timing

From: Prabhakar Ragde (plragde at uwaterloo.ca)
Date: Fri Feb 15 13:00:21 EST 2008

Carl Eastlund wrote:

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

Sure, but it wouldn't be faster. And I don't see a "natural" way to 
write a fast non-tail-recursive reverse.

`flatten' is a better example, since naive structural recursion gives 
O(n^2) time, but it's not necessary to use tail recursion to get this 
down to O(n). Trying to write it tail-recursively will probably get you 
there, but there's an easier way. --PR


Posted on the users mailing list.