Karlis wrote:
> > The reason for this is that in recursive functions, the stack has a
> > very definite pattern to it, where each stack frame is a function of
> > the previous frame. If this function is invertible, then you only need
> > to store the bottommost stack frame. The rest of the stack can be
> > regenerated from this by applying the inverse transformation.
>
> Well, isn't that the case in which you can easily transform recursion to
> iteration? There are tasks you can solve with recursion _or_ iteration.
The case where you can *easily* transform recursion into iteration is
tail-end recursion. This is where the return value from a function is
the value returned from the recursive call.
For example:
int factorial(int n)
{
if (n <= 1)
return 1;
return n * factorial(n - 1);
}
isn't tail-end recursive, but it can be put into a form which is,
i.e.:
int factorial2(int a, int n)
{
if (n <= 1)
return a;
return factorial2(n * a, n - 1);
}
int factorial(int n)
{
return factorial2(1, n);
}
In this case, the tail-end of the factorial2() function would be
naïvely compiled to:
call factorial2
ret
but this can be optimised to just
jmp factorial2
which turns the recursion into iteration, eliminating the need for a
return stack of depth n.
Note that the function's parameters aren't needed after the recursive
call has returned, so they can be modified `in-place'.
> I can only think of big use for this in Prolog, where you used recursion
> only.
Tail end recursion is central to functional languages (e.g. ML,
Miranda, Hope, Haskell). These don't support the notion of mutable
state, so you have to express iteration as recursion (although the
compiler will implement it as iteration when possible).
However, Prolog mainly performs branched recursion (it can make
multiple recursive calls at each level), which can't be optimised in
this way.
Nor can the `stackless recursion' techniques be applied to Prolog. The
nature of `search' algorithms means that you have to store the
previous state on a stack, as the transformation isn't invertible.
--
Glynn Clements <[EMAIL PROTECTED]>
