Tuukka Toivonen wrote:
> > Stack Free Recursion
> > Otto J. A. Smith
> > Sept 29, 1995
>
> Sorry to say this, but there is *no* such thing as stackless
> recursion, nor stackless function call at all. This is because
> when some function is called, the return address is saved
> in the *stack*.
That's an implementation issue. For instance, architectures based upon
the ARM chip implement function calls using the `BL' (branch with
link) instruction, which saves the return address in a register (R14).
It is the responsibility of the caller to preserve the contents of R14
prior to calling other functions. For a function which is a leaf-node
in the call-graph (one that doesn't call any other functions), this
eliminates the need to reference memory.
> >int factorial() //Pass x as Global No data Stack
> >{
> > int prod;
>
> Local variables in a function are stored in -- guess where -- stack.
Note that the variable isn't actually assigned to until after the
recursive call returns. Consequently, `prod' can be made static.
> > x = x-1; //A function
> > if(x+1 < = 0) prod = 1;
> > else prod = (x+1) * factorial(); //The recursive call
>
> The result for x+1 is calculated in register, which is then saved
> into *stack* before calling the function again (or maybe just variable
> x is saved into stack, but something in any case is saved into stack).
Again, this is an implementation issue. On RISC architectures (which
typically have many more registers than the 80x86), function
parameters are often passed in registers.
> > x = x+1; //A function inverse
> >return prod;
> >}
>
> The thing about what you were talking was not *stackless* recursion,
> but in fact, *parameterless* recursion. The parameters are passed
> in GCC using stack, which is avoided this way but they could be passed
> in registers *or* as global variables too. But stack is needed anyway.
No, not always. The point of this paper was that if the transformation
which is applied to the parameters can be inverted (and in many cases
it can), you don't need to use a stack.
Clearly, this can't always be done (e.g. searching a tree which
doesn't have `up' pointers), but in many cases it can.
--
Glynn Clements <[EMAIL PROTECTED]>
