On Thu, 8 Jul 2004, Andreas Rossberg wrote:

> David Brown wrote:
> > 
> > In some functional languages (Scheme, specifically), tail recursion is
> > required to be implemented iteratively.  It is a common enough idiom,
> > and easy enough to implement, that it is generally done in functional
> > languages.  In fact, gcc does it in C, with enough optimization.
> 
> The latter is, to a certain extent, a myth.
> 
> First, you have to distinguish between simple tail *recursion*, and the 
> much more general concept of tail *call*. I believe Scheme requires to 
> fully optimize the latter, and so it is done by all decent FPL 
> implementations. GCC does not do that, already falling short of mutually 
> recursive functions, IIRC.

GCC has started optimizing tail calls in 3.x.  

I compiled:

int fib(int a, int b, int n) {
    if (n <= 1) {
        return b;
    } else {
        return fib(b, a+b, n-1);
    }
}

with gcc 3.2.2 -O2, and got:

.globl fib
        .type   fib,@function
fib:
        pushl   %ebp
        movl    %esp, %ebp
        movl    12(%ebp), %ecx
        pushl   %ebx
        movl    16(%ebp), %edx
        movl    8(%ebp), %ebx
        .p2align 2,,3
.L4:
        cmpl    $1, %edx
        jle     .L5
        leal    (%ecx,%ebx), %eax
        decl    %edx
        movl    %ecx, %ebx
        movl    %eax, %ecx
        jmp     .L4
.L5:
        movl    %ecx, %eax
        popl    %ebx
        leave
        ret

Notice that it's turned the tail call recursion into a loop.  I don't 
recall it doing this back in 2.95 or 2.96, so it's a pretty recent 
improvement, but it does now exist.

What it's limits are, I haven't determined, but it does exist.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners