Subj : Re: When are recursive functions needed?
To   : comp.programming
From : Rob Thorpe
Date : Tue Oct 04 2005 04:22 am

Tatu Portin wrote:
> Gene wrote:
> > This is angels dancing on pins.  At a certain level of abstraction, of
> > course iteration and recursion are the same thing.
> >
> > The question author was clearly asking about programming styles in
> > imperative languages.  Recursive in this context means "using self- or
> > mutually-referential function/procedure calls," and iterative means
> > "using looping structures."  It is certainly always possible to
> > translate from the former to the latter (and back).
> >
> > CPS only hides the mechanism for storing intermediate results.  It's
> > not a priori any more or less "recursive" than a loop and a stack or a
> > self-referential call.  When you compile to code, the RTS will have
> > either a stack or a heap where closures store the same data as would
> > have been contained in what you call a "manual stack."
> >
>
> So, in more complex systems recursion is a way of presentation,
> different from iterative,

Yes, many functional languages optimize recursion, normally by
converting it into iteration.

> because both solutions are as much efficient.

No, almost always iteration is more efficient.

> The problem translates to: "To which extent iterative solution is more
> efficient than recursive?"

Depends a lot on the problem.  For some problems there's almost no
difference, for others recursion is extremely expensive.

There may be a very few where recursion is faster.  I don't know of any
though.

> By the way, does C89 say anything about how large stack can be?
> Maximum size of stack would be limiting factor, at least in old (very
> old) compilers.

There are no limits in most modern systems.  It was once a problem in
DOS I think.

The problem here is more the function you write.  If you write a
function that allocates 128 bytes on the stack, then call it
recursively ten thousand times you're nearly OK.  Call it a few
millions of times and you will use a lot of RAM.

Recursion is used when it's clearer and doesn't harm performance.

.