Subj : Re: Are recursive functions ever needed?
To   : comp.programming
From : Roger Willcocks
Date : Sun Oct 02 2005 07:42 pm


"Tatu Portin" <axel86@mbnet.fi> wrote in message 
news:S6v%e.208$nZ1.35@read3.inet.fi...
> Are recursive functions ever needed, i.e. cannot you just replace them 
> with iterative clauses?
>
> Example:
>
> b = func (func (func (a)))
>
> compared to:
>
> b = a;
> for (i = 0; i < 3; i++)
>   {
>     b = func (b);
>   }

That's an example of a tail recursive call, where the last thing func does 
is call itself. It can be converted to a simple iteration. Written as a 
recursive call it would look something like:

int func(int depth, int b)
{
    if (depth >= 3) return b;
    /* do something with b */
    return func(depth + 1, b);
}

b = func(0, a);

But recursive functions can be more complicated. Consider the slight 
variation:

int func(int depth, int b)
{
    if (depth >= 3) return b;
    b = func(depth + 1, b);
    /* do something with b */
    return b;
}

where the most deeply nested 'do something' gets performed first. This can 
still be converted to an iteration, but it needs more thought than the first 
example.

More generally a recursive routine needs a stack, so that values used on the 
way 'down' are still available for use on the way back 'up'.

--
Roger

.