From: Robert.Koepferl@...
Date: 2003-10-17T00:39:44+09:00
Subject: Antwort: Re: Syntax for end recursion





Yes, tail means the same as my end.
You're right. I oversaw the multiply, wich gets of course the last
instruction.

thx




> does ruby have a syntax or some way to tell it to use end recursion.
> I tried to write a recoursive factorial function (to test BigNum).
However
> the stack is limited (of course).
>
>     def fak(z)
>         return 1 if z<=1;
>         z* fak(z-1) if z>1;
>     end
>
> in some languages it's possible "to return first and then invoke the last
> instruction"

Maybe I'm wrong, but isn't that impossible in this case since the last
instruction is the multiply and the recursive call is the one-to-last
instruction? You can make it tail recursive (is that the same as end
recursive?) by using an accumulating parameter:

def fac(z)
    fac_acc(1, z)
end

def fac_acc(n, z)
    return n if z <= 1
    fac_acc(n * z, z - 1)
end

This is tail recursive, and you can do the tail recursion optimization
since the recursive call is the last 'instruction' in the method. But
apparently ruby doesn't do the optimization and still runs out of stack
space. Don't know the answer to that I'm afraid. Note that many languages
like Prolog, Scheme, Lisp, Haskell, ... can do the tail recursion
optimization without user directives. Even .NET supports it. There it is
the compiler that finds out, but technically that's easy if the programmer
makes his recursive functions tail recursive.

Peter