Subj : Re: Are recursive functions ever needed?
To   : comp.programming
From : Rob Thorpe
Date : Sat Oct 01 2005 09:50 am

Tatu Portin wrote:
> Aleya Roe wrote:
> >>Are recursive functions ever needed, i.e. cannot you just replace them
> >>with iterative clauses?
> >
> > Yes, you can always convert recursion to iteration. But it's not always
> > worth the effort since all but the simplest examples of recursion
> > require you to explicitly use a stack to save the algorithm state that
> > would otherwise be saved by making a recursive call. Sometimes the
> > algorithm makes things easier and with a lot of creativity you can
> > figure out how to avoid the stack, but examples like that are rare.
> >
> >
> >>b = func (func (func (a)))
> >
> > That's not really recursion though, unless this statement is inside the
> > definition of func. You're just calling the function three times.
> > That's easy to turn into iteration.
> >
>
>
> Well, my problem here seems to be lack of good examples where
> recursion is needed. Would anybody provide some?

No, as mentioned above recursive calls are never needed per se.  They
can always be replaced by other control structures.

It's used when it's the most simple solution to the problem.  For
example in a programming language parser there is often part that
mathematical parses expressions.  It's probably complex and calls many
other functions.  Consider the parentheses in a mathematical
expression, inside the parentheses is another complete expression.  The
simplest way of dealing with parentheses is for the expression parser
to call itself recursively on the data inside them.  It may be some
function called by the expression parser that does this (mutual
recursion).

See for example
http://groups.google.co.uk/group/comp.sources.misc/browse_frm/thread/762bf81dd3363c91/e7a49b17100f5ea0?lnk=st&q=cfoogol&rnum=2&hl=en#e7a49b17100f5ea0

.