Professional Web Applications Themes

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. #1

    Default 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. #2

    Default 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. #3

    Default 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. #4

    Default 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. #5

    Default 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

Similar Threads

  1. Is Recursion Allowed?
    By DaveHCYJ in forum Coldfusion - Advanced Techniques
    Replies: 2
    Last Post: May 16th, 04:29 PM
  2. 256 levels of recursion??
    By floyduk in forum Macromedia Flash Actionscript
    Replies: 5
    Last Post: March 6th, 04:19 PM
  3. Size of dir (with recursion)
    By Jesper Noehr in forum PERL Beginners
    Replies: 4
    Last Post: December 29th, 11:08 PM
  4. Recursion
    By Jeff Westman in forum PERL Beginners
    Replies: 15
    Last Post: November 4th, 12:18 AM
  5. Antwort: Syntax for end recursion
    By Robert.Koepferl@de.gi-de.com in forum Ruby
    Replies: 0
    Last Post: October 16th, 03:39 PM

Bookmarks

Posting Permissions

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139