On Fri, 26 Jun 1998, Glynn Clements 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.
>> 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.
>> > 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.
Yep, and on x86 and GCC with __attribute__((regparm(x))). But if you
look the source code carefully, you'll notice that the function
call didn't have any parameters. :)
>> 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.
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...)
--
| Tuukka Toivonen <[EMAIL PROTECTED]> [PGP public key
| Homepage: http://www.ee.oulu.fi/~tuukkat/ available]
| Try also finger -l [EMAIL PROTECTED]
| Studying information engineering at the University of Oulu
+-----------------------------------------------------------
