Re: [SLUG] [PIG] Recursive vs. iterative

From: Eben King (eben01@verizon.net)
Date: Tue Jul 11 2006 - 13:24:38 EDT


On Tue, 11 Jul 2006, Dylan William Hardison wrote:

> On 7/10/06, Eben King <eben01@verizon.net> wrote:
>> On Mon, 10 Jul 2006, Dylan William Hardison wrote:
>> > Spake Eben King on Friday, July 07, 2006 at 01:14PM -0400:
>> >> The prof said any recursive algorithm can be turned into a non-recursive
>> >> algorithm, which is reasonable, as that's what compiled code with loops
>> >> completely unrolled is.
>> >
>> > This is somewhat misleading.
>> >
>> > Any recursive function can be written using iteration, however this does
>> > not always result in faster code.
>>
>> Sure, you can make any algorithm worse.
>
> Using iteration generally makes an algorithm look worse, too. ;)

Agreed. He didn't say (and I didn't mean to imply) that changing an
algorithm from recursive to iterative always made it clearer, only that it
was possible.

>> > The problem with recursive functions is not the recursion itself, but
>> > the stack space used by each call.
>>
>> True. You have demonstrated a way around this, with tail recursion. I
>> don't know if it's applicable to every algorithm, but if not, you're no
>> worse off for trying.
>>
> You can't use tail recursion for every instance of recursion. However,
> where you can't use it, writing it with iteration isn't (usually) a
> net win. That was my point.

OK.

-- 
-eben     QebWenE01R@vTerYizUonI.nOetP     http://royalty.no-ip.org:81
Are you confident that you appear to be professional in your electronic
communication?  Consider this: A: No
                                Q: Can I top post? from nick@xx.co.uk
-----------------------------------------------------------------------
This list is provided as an unmoderated internet service by Networked
Knowledge Systems (NKS).  Views and opinions expressed in messages
posted are those of the author and do not necessarily reflect the
official policy or position of NKS or any of its employees.



This archive was generated by hypermail 2.1.3 : Fri Aug 01 2014 - 20:38:17 EDT