Tuukka Toivonen wrote:
> > Tuukka Toivonen wrote:
> > >
> > > Sorry to say this, but there is *no* such thing as stackless
> > > recursion, nor stackless function call at all. This is because
> ------------------------------
>
> Okay, I was wrong. Leaf-node function doesn't have to use stack
> (as you explained). But I still think a recursed function
> needs stack. If a recursed function is reformed to not use stack,
> in my opinion it can not be said to be recursed function anymore
> (because it will have loops instead of recursion).
> If you disagree, please give an example of recursed function
> without stack usage :)
> At least if you recurse with GCC, the return address will be pushed
> into stack always AFAIK.
Sure, but you can simulate a function call. I've had to do this when
writing recursive functions in Java, which has a pitifully small
stack.
> > > 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.
>
> Recursed function calls itself, so it has to save the return address.
> No matter if the function call machine language instruction saves
> the return address automatically into stack, or if the function
> saves it explicitly, it has to be saved anyway. If the function calls
> another function _non-recursively_, the return address could be saved
> into a static variable, thus avoiding stack.
But in the case of non-branched recursion, the stack basically holds
the return address corresponding to the original non-recursive call,
followed by N occurrences of the address following the recursive call,
so you only really need to store the integer N.
For branched recursion, you can apply the same techniques that the
paper describes to eliminate the need to store local variables on the
stack. If you can deduce which occurrence of the recursive call you're
returning from, you don't need to store the return address.
I don't have an example to hand, but I will generate one.
> > > But stack is needed anyway.
> [for recursed functions]
> >
> > 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.
>
> The original message was talking how to make recursion without using
> stack. The all examples which were supposed to demonstrate it, in fact
> used stack.
Actually, the first sentence of the article was:
Abstract: A method of building recursive functions in systems that
don't have a data stack is presented. We illustrate its use with a
^^^^
The factorial example doesn't necessarily use any data stack. It isn't
guaranteed that the variable `prod' will be stored on the stack. It
could be stored in a register. As it hasn't been assigned a value
prior to the recursive call, it doesn't need to be saved before making
the call.
> If you take a recursed function and convert it so that it doesn't
> use stack, _it isn't recursed anymore_. (I think. I don't have proof...)
That's a definitition issue. It's not something that you can prove or
disprove. If you refer to a mathematical text on recursion, it won't
make any mention of a `stack'. That is an implementation issue.
A recursive function is one which is defined in terms of itself.
Whilst the most straightforward method for implementing such functions
is to use a stack, the paper shows that it is not always necessary.
The point is that many recursive functions can be implemented with
O(1) space complexity, rather than the O(n) space complexity obtained
when using a stack.
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.
--
Glynn Clements <[EMAIL PROTECTED]>
