Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!mcsun!ukc!newcastle.ac.uk!turing!ncmh From: Chris.Holt@newcastle.ac.uk (Chris Holt) Newsgroups: comp.lang.scheme Subject: Re: Tail recursion - it's not just for breakfast any more. Message-ID: <1991May14.134257.16696@newcastle.ac.uk> Date: 14 May 91 13:42:57 GMT References: Sender: news@newcastle.ac.uk Distribution: comp Organization: University of Newcastle upon Tyne, UK, NE1 7RU Lines: 21 carlton@husc10.harvard.edu (david carlton) writes: >Everybody knows that writing procedures in a tail-recursive way is a >Good Thing. I'm curious as to just how much of a good thing people >thing it is, though... > What if the tail-recursive version takes time order of >the square of the length of its input, say, while the other version >takes time order the length of its input? > Can >one in fact come up with a procedure whose fastest tail-recursive >implementation has slower order than its fastest implementation? What >about memory usage? Aren't tail-recursive sorts bounded by o(n**2), while doubly-recursive sorts bounded by o(n*log n)? [Unless you're Dan Bernstein, in which case radix is linear :-)]. ----------------------------------------------------------------------------- Chris.Holt@newcastle.ac.uk Computing Lab, U of Newcastle upon Tyne, UK ----------------------------------------------------------------------------- "And when they die by thousands why, he laughs like anything." G Chesterton