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

From: Dylan William Hardison (dylanwh@gmail.com)
Date: Tue Jul 11 2006 - 07:13:00 EDT


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

> > 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.
Sorry if my email was a bit windy and unclear.
-----------------------------------------------------------------------
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:08 EDT