Andrea Arcangeli wrote:
> > > 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
>
> To be more precise is _only_ a GCC issue. GCC i386 doesn' t use registers
> for passing argument to functions only for historical reasons and because
> other i386 compilers uses stack (so if GCC would do different things
> object and libs couldn' t be sharded between compilers). For example
> syscalls on i386 use registers to pass parameters to the kernel and I can'
> t see no differences between `int 0x80' and `call' asm inst...
Right. Many DOS compilers offered a choice of calling convention.
However, once you're on an OS which features `standard' libraries, you
are generally stuck with the OS' choice of calling convention.
> > > 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.
>
> And infact the great avantage of recursion is when we can' t avoid the use
> of the stack. For compute a factorial the complexity is so low that there'
> s no need to use recursion... I think that the great thing of the
> recursion is the stack ;-).
Well, in an ideal world, the compiler would convert tail recursion to
iteration, so you could use either paradigm without affecting the
underlying code (functional languages need to do this, as you have to
use recursion).
For the more involved case of branched recursion, which would
typically use a stack but could be implemented using the techniques
described in the `stackless recursion' paper, it isn't (IMHO)
realistic to expect the compiler to be able to eliminate the use of
the stack.
In most cases, it isn't worth paying the legibility penalty to
eliminate the use of the stack. However, I can imagine that it could
be a useful technique in applications where space complexity has to be
taken into account, e.g. mission-critical systems, where you can't
just assume that sufficient memory is available, and add a disclaimer
to the effect that the program will fail if there isn't (which is
basically the way that most programs are written).
--
Glynn Clements <[EMAIL PROTECTED]>
