Syntax for end recursion - Ruby

Hi, 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" Not that I need it, I'm just interested....

1. Syntax for end recursion

Hi,
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"
Not that I need it, I'm just interested.

Robert.Koepferl@de.gi-de.com Guest

2. Re: Syntax for end recursion

> 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 aculating 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

Peter Guest

3. Re: Syntax for end recursion

<Robert.Koepferlde.gi-de.com> schrieb im Newsbeitrag
news:OF5ABC6057.5E91ED4E-ONC1256DC1.0052D583gdm.de...
>
>
>
>
> Hi,
> does ruby have a syntax or some way to tell it to use end recursion.
No.
> 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"
> Not that I need it, I'm just interested.
From my experience you're better off in Ruby if you omit recursion because
the stack is not really deep:

def foo(n); puts n; foo(n+1); end

foo(1) =>
....

15381
15382
15383
15384
SystemStackError: stack level too deep
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
.... 15354 levels...
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):1:in `foo'
from (irb):2irb(main):003:0>

This isn't sufficient if you want to create heavily numeric applications.

robert

Robert Klemme Guest

4. Re: Syntax for end recursion

"Peter" wrote:
....
> 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 aculating 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.
Hi,

check out the ruby-optimizer extension
[url]http://raa.ruby-lang.org/list.rhtml?name=ruby-optimizer[/url]
It pretty much does what you describe. Unfortunately it
does not work with 1.8. (I used it with 1.7 and it did
improve both speed and stack-limit substantially).

/Christoph

Christoph Guest

5. Re: Syntax for end recursion

Hi All,
I trust all is well?
I currently have a job opportunity available, and am looking for a Web App Developer with Ruby experience for a role based in Central London.
Sam Preece Guest

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•