SystemStackError: stack level too deep > how make it deeper?

Discussion in 'Ruby' started by Joshua Muheim, Sep 30, 2009.

  1. Hi all

    I have a recursive algorith that must run until it finds the result:

    def p(n)
    n * (3 * n - 1) / 2
    end

    def h(n)
    n * (2 * n - 1)
    end

    def find_next_match(p, h)
    result_p = p(p + 1)
    result_h = h(h + 1)
    if result_p == result_h # Resultat gefunden!
    return result_p
    else
    result_p < result_h ? p += 1 : h += 1

    puts "find next match for p=#{p} (#{result_p}) and h=#{h}
    (#{result_h})"
    find_next_match(p, h)
    end
    end

    The task is to find the next pair of p and h that result in the same
    number. The first pair is 165 and 143, so I run it with these arguments:

    puts find_next_match(165, 143)

    Sadly, after some seconds, Ruby throwns a SystemStackError:

    SystemStackError: stack level too deep
    method p in uebung-2-1.rb at line 2
    method find_next_match in uebung-2-1.rb at line 10
    method find_next_match in uebung-2-1.rb at line 18
    at top level in uebung-2-1.rb at line 22
    copy output
    Program exited with code #1 after 8.29 seconds.

    But I'd like to run it and run it and run it without this limitation. Is
    there a workaround for this, so I can change the stack level maximum?

    Thanks a lot for help
    Josh
    --
    Posted via http://www.ruby-forum.com/.
     
    Joshua Muheim, Sep 30, 2009
    #1
    1. Advertising

  2. [Note: parts of this message were removed to make it a legal post.]

    On Wed, Sep 30, 2009 at 3:47 PM, Joshua Muheim <> wrote:

    > Hi all
    >
    > I have a recursive algorith that must run until it finds the result:
    >
    > def p(n)
    > n * (3 * n - 1) / 2
    > end
    >
    > def h(n)
    > n * (2 * n - 1)
    > end
    >
    > def find_next_match(p, h)
    > result_p = p(p + 1)
    > result_h = h(h + 1)
    > if result_p == result_h # Resultat gefunden!
    > return result_p
    > else
    > result_p < result_h ? p += 1 : h += 1
    >
    > puts "find next match for p=#{p} (#{result_p}) and h=#{h}
    > (#{result_h})"
    > find_next_match(p, h)
    > end
    > end
    >
    > The task is to find the next pair of p and h that result in the same
    > number. The first pair is 165 and 143, so I run it with these arguments:
    >
    > puts find_next_match(165, 143)
    >
    > Sadly, after some seconds, Ruby throwns a SystemStackError:
    >
    > SystemStackError: stack level too deep
    > method p in uebung-2-1.rb at line 2
    > method find_next_match in uebung-2-1.rb at line 10
    > method find_next_match in uebung-2-1.rb at line 18
    > at top level in uebung-2-1.rb at line 22
    > copy output
    > Program exited with code #1 after 8.29 seconds.
    >
    > But I'd like to run it and run it and run it without this limitation. Is
    > there a workaround for this, so I can change the stack level maximum?
    >
    > Thanks a lot for help
    > Josh
    > --
    > Posted via http://www.ruby-forum.com/.
    >
    >

    Rewrite it to not be recursive.

    Jason
     
    Jason Roelofs, Sep 30, 2009
    #2
    1. Advertising

  3. Joshua Muheim, Sep 30, 2009
    #3
  4. On Sep 30, 2009, at 4:30 PM, Joshua Muheim wrote:

    > Jason Roelofs wrote:
    >> On Wed, Sep 30, 2009 at 3:47 PM, Joshua Muheim <> wrote:
    >>
    >>> end
    >>> (#{result_h})"
    >>>
    >>>
    >>> Thanks a lot for help
    >>> Josh
    >>> --
    >>> Posted via http://www.ruby-forum.com/.
    >>>
    >>>

    >> Rewrite it to not be recursive.
    >>
    >> Jason

    >
    > That's not very helpful... Some sort of tautology, isn't it. ;-)
    > http://en.wikipedia.org/wiki/Tautology




    Or a problem from Project Euler... ;-)
    http://projecteuler.net/index.php?section=problems&id=45

    real 0m0.639s
    user 0m0.623s
    sys 0m0.008s

    And my solution (in Ruby) could even be made more efficient. However,
    it uses a constant amount of space (i.e., no recursion at all, just
    some nested loops).

    -Rob

    Rob Biedenharn http://agileconsultingllc.com
     
    Rob Biedenharn, Sep 30, 2009
    #4
  5. Joshua Muheim

    Gary Wright Guest

    On Sep 30, 2009, at 3:47 PM, Joshua Muheim wrote:
    > But I'd like to run it and run it and run it without this
    > limitation. Is
    > there a workaround for this, so I can change the stack level maximum?


    I'm assuming a Unix/Linux environment...

    The stack limitation is enforced by the OS. You'll have to change
    the limits in your shell so that when the Ruby interpreter is started
    it is allowed to grow a larger stack.

    Try this first:
    $ ruby -e 'def foo(count); print "#{count} "; foo(count+1); end; foo(0)'

    to see how deep your stack can go. Bash, ksh, and zsh all have the
    ulimit command for setting process resources (such as the stack size):

    $ ulimit -a

    will show you the current limits and

    $ ulimit -s 16384

    will change your stack size to 16384k (for example).

    Now run the ruby one liner I showed above and you should see that the
    program recurses deeper before failing.

    Gary Wright
     
    Gary Wright, Sep 30, 2009
    #5
  6. > Or a problem from Project Euler... ;-)
    > http://projecteuler.net/index.php?section=problems&id=45
    >
    > real 0m0.639s
    > user 0m0.623s
    > sys 0m0.008s
    >
    > And my solution (in Ruby) could even be made more efficient. However,
    > it uses a constant amount of space (i.e., no recursion at all, just
    > some nested loops).
    >
    > -Rob
    >
    > Rob Biedenharn http://agileconsultingllc.com
    >


    Yeah, it's from Project Euler (our professor is just too lazy to create
    his own tasks...).

    Your solution sounds interesting; would you mind posting it here? I
    won't steal it; we don't have to submit perfect solutions, it's more
    sort a thinking-task where we're told to deliver possible solutions.
    --
    Posted via http://www.ruby-forum.com/.
     
    Joshua Muheim, Sep 30, 2009
    #6
  7. [Note: parts of this message were removed to make it a legal post.]

    On Wed, Sep 30, 2009 at 4:56 PM, Joshua Muheim <> wrote:

    > > Or a problem from Project Euler... ;-)
    > > http://projecteuler.net/index.php?section=problems&id=45
    > >
    > > real 0m0.639s
    > > user 0m0.623s
    > > sys 0m0.008s
    > >
    > > And my solution (in Ruby) could even be made more efficient. However,
    > > it uses a constant amount of space (i.e., no recursion at all, just
    > > some nested loops).
    > >
    > > -Rob
    > >
    > > Rob Biedenharn http://agileconsultingllc.com
    > >

    >
    > Yeah, it's from Project Euler (our professor is just too lazy to create
    > his own tasks...).
    >
    > Your solution sounds interesting; would you mind posting it here? I
    > won't steal it; we don't have to submit perfect solutions, it's more
    > sort a thinking-task where we're told to deliver possible solutions.
    > --
    > Posted via http://www.ruby-forum.com/.
    >
    >

    So I get put down for suggesting the very thing Rob did, who gets praise?

    If you don't want long-running code crashing, don't do it recursive in a
    language like Ruby. You will run out of memory, and you will crash. There
    are very few, if any, algorithms normally written recursively that can't be
    written iteratively.

    Jason
     
    Jason Roelofs, Sep 30, 2009
    #7
  8. > So I get put down for suggesting the very thing Rob did, who gets
    > praise?
    >
    > If you don't want long-running code crashing, don't do it recursive in a
    > language like Ruby. You will run out of memory, and you will crash.
    > There
    > are very few, if any, algorithms normally written recursively that can't
    > be
    > written iteratively.
    >
    > Jason


    OK, thank you. :) At least, this a useful piece of information, I don't
    have much experience in writing algorithms...

    Anyway, I will hand in my solution above; in theory it works. :)
    --
    Posted via http://www.ruby-forum.com/.
     
    Joshua Muheim, Sep 30, 2009
    #8
  9. On Sep 30, 2009, at 5:02 PM, Jason Roelofs wrote:
    > On Wed, Sep 30, 2009 at 4:56 PM, Joshua Muheim <> wrote:
    >>> Or a problem from Project Euler... ;-)
    >>> http://projecteuler.net/index.php?section=problems&id=45
    >>>
    >>> real 0m0.639s
    >>> user 0m0.623s
    >>> sys 0m0.008s
    >>>
    >>> And my solution (in Ruby) could even be made more efficient.
    >>> However,
    >>> it uses a constant amount of space (i.e., no recursion at all, just
    >>> some nested loops).
    >>>
    >>> -Rob
    >>>
    >>> Rob Biedenharn http://agileconsultingllc.com
    >>>

    >>
    >> Yeah, it's from Project Euler (our professor is just too lazy to
    >> create
    >> his own tasks...).
    >>
    >> Your solution sounds interesting; would you mind posting it here? I
    >> won't steal it; we don't have to submit perfect solutions, it's more
    >> sort a thinking-task where we're told to deliver possible solutions.
    >> --
    >> Posted via http://www.ruby-forum.com/.
    >>
    >>

    > So I get put down for suggesting the very thing Rob did, who gets
    > praise?
    >
    > If you don't want long-running code crashing, don't do it recursive
    > in a
    > language like Ruby. You will run out of memory, and you will crash.
    > There
    > are very few, if any, algorithms normally written recursively that
    > can't be
    > written iteratively.
    >
    > Jason



    I'm on exactly the same page as Jason. The problem does not even need
    a recursive algorithm. (Well, except that it's not the Ruby language
    that is recursive, but the algorithm that you attempted to write *in*
    Ruby.)

    Your attempt isn't really too far off, however. I'll point out that
    your algorithm is "tail recursive" and that's partly why you run out
    of stack space in a language like Ruby, but in a language optimized
    for tail recursion it might have worked. Think about what that means
    and how you could restructure your code to avoid making a new function
    call if the current pair is not a solution. (Hint: How would you
    search for the solution standing at a blackboard/whiteboard?)

    -Rob

    Rob Biedenharn http://agileconsultingllc.com
     
    Rob Biedenharn, Sep 30, 2009
    #9
  10. Joshua Muheim

    Ken Bloom Guest

    On Thu, 01 Oct 2009 04:47:28 +0900, Joshua Muheim wrote:

    > Hi all
    >
    > I have a recursive algorith that must run until it finds the result:
    >
    > def p(n)
    > n * (3 * n - 1) / 2
    > end
    >
    > def h(n)
    > n * (2 * n - 1)
    > end
    >
    > def find_next_match(p, h)
    > result_p = p(p + 1)
    > result_h = h(h + 1)
    > if result_p == result_h # Resultat gefunden!
    > return result_p
    > else
    > result_p < result_h ? p += 1 : h += 1
    >
    > puts "find next match for p=#{p} (#{result_p}) and h=#{h}
    > (#{result_h})"
    > find_next_match(p, h)
    > end
    > end


    The code you have posted is tail recursive, which means that the original
    function call does nothing after it makes the recursive call, and returns
    the recursive call's return value. Many compilers can optimize the code
    to set up new values for the parameters, and then jump back to the
    beginning of the function (with something like a goto), reusing the
    current stack frame. (This is called tail call optimization.)

    Ruby does not perform tail call optimization, because it prefers to keep
    track of the exact call stack in case you raise an exception. So you need
    to invent the loop to do this yourself.

    Something like

    def find_next_match(p,h)
    loop do
    #do stuff
    #wherever you would have a recursive call
    # just update the values of p and h respectively
    end
    end

    Alternatively, it appears you can enable tail call recursion in Ruby 1.9
    changing a #define in the source code and recompiling. See http://
    redmine.ruby-lang.org/issues/show/1256

    You can also accomplish tail call optimization in Ruby 1.9 without
    recompiling the interpreter. You can include the algorithm as a string,
    compile it to an instruction sequence with a dynamic option to enable
    tail call optimization, and eval that instruction sequence. The
    instructions are given at the above link.

    --
    Chanoch (Ken) Bloom. PhD candidate. Linguistic Cognition Laboratory.
    Department of Computer Science. Illinois Institute of Technology.
    http://www.iit.edu/~kbloom1/
     
    Ken Bloom, Oct 1, 2009
    #10
  11. On Wednesday 30 September 2009 04:17:31 pm Rob Biedenharn wrote:

    > your algorithm is "tail recursive" and that's partly why you run out
    > of stack space in a language like Ruby, but in a language optimized
    > for tail recursion it might have worked.


    Probably would have.

    The other thing is to note that the question the subject is asking should
    never be asked. If you're in a language that optimizes tail-recursing, it's
    probably about as efficient as a loop.

    If you're in a language that doesn't optimize tail-recursing, the last thing
    you want to do is increase the size of the stack. That would just give you the
    same problem again later, and waste tons of RAM.
     
    David Masover, Oct 1, 2009
    #11
  12. Joshua Muheim

    Tony Arcieri Guest

    [Note: parts of this message were removed to make it a legal post.]

    On Wed, Sep 30, 2009 at 1:55 PM, Jason Roelofs <>wrote:

    > Rewrite it to not be recursive.
    >


    That advice is about as useful as "Rewrite it in a language other than Ruby"


    --
    Tony Arcieri
    Medioh/Nagravision
     
    Tony Arcieri, Oct 1, 2009
    #12
  13. Joshua Muheim

    Josh Cheek Guest

    [Note: parts of this message were removed to make it a legal post.]

    On Wed, Sep 30, 2009 at 3:56 PM, Joshua Muheim <> wrote:

    > > Or a problem from Project Euler... ;-)
    > > http://projecteuler.net/index.php?section=problems&id=45
    > >
    > > real 0m0.639s
    > > user 0m0.623s
    > > sys 0m0.008s
    > >
    > > And my solution (in Ruby) could even be made more efficient. However,
    > > it uses a constant amount of space (i.e., no recursion at all, just
    > > some nested loops).
    > >
    > > -Rob
    > >
    > > Rob Biedenharn http://agileconsultingllc.com
    > >

    >
    > Yeah, it's from Project Euler (our professor is just too lazy to create
    > his own tasks...).
    >
    > Your solution sounds interesting; would you mind posting it here? I
    > won't steal it; we don't have to submit perfect solutions, it's more
    > sort a thinking-task where we're told to deliver possible solutions.
    > --
    > Posted via http://www.ruby-forum.com/.
    >
    >

    Which PE question is it? I've solved 140 of them, the computer that had the
    majority of my solutions ended up dying, and a large number of them are
    solved in Java, but there is no harm in checking to see if I have the
    solution on this computer, in Ruby.
    -Josh
     
    Josh Cheek, Oct 1, 2009
    #13
  14. * Tony Arcieri <> (05:25) schrieb:

    > [Note: parts of this message were removed to make it a legal post.]
    >
    > On Wed, Sep 30, 2009 at 1:55 PM, Jason Roelofs <>wrote:
    >
    >> Rewrite it to not be recursive.

    >
    > That advice is about as useful as "Rewrite it in a language other than Ruby"


    But it's the only answer there is. Unrecognized tail recursion will kill
    every stack.

    def find_next_match(p, h)
    loop do
    result_p = p(p + 1)
    result_h = h(h + 1)
    if result_p == result_h # result found!
    return result_p
    if result_p < result_h
    p += 1
    else
    h += 1
    end
    puts "find next match for p=#{p} (#{result_p}) and h=#{h} (#{result_h})"
    end
    end

    mfg, simon .... not tried
     
    Simon Krahnke, Oct 1, 2009
    #14
  15. On Thursday 01 October 2009 05:05:13 am Simon Krahnke wrote:
    > * Tony Arcieri <> (05:25) schrieb:
    > > [Note: parts of this message were removed to make it a legal post.]
    > >
    > > On Wed, Sep 30, 2009 at 1:55 PM, Jason Roelofs

    <>wrote:
    > >> Rewrite it to not be recursive.

    > >
    > > That advice is about as useful as "Rewrite it in a language other than
    > > Ruby"


    Somehow, I think rewriting a tail-recursive algorithm to not be tail-recursive
    is much, much faster than translating the algorithm to another language,
    especially if it's part of a larger program.

    It is a bit like, when you go from C to Ruby, you learn to use each loops
    instead of for loops. An argument could be made that tail-recursion isn't
    idiomatic Ruby.

    > But it's the only answer there is. Unrecognized tail recursion will kill
    > every stack.


    Technically, it's not -- Ruby _can_ do tail recursion. It's just not trivial
    to turn on, not portable, and I believe disables some debugging features.
     
    David Masover, Oct 1, 2009
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jesper Olsen
    Replies:
    7
    Views:
    576
    Van Jacques
    Jan 16, 2004
  2. Sam Roberts
    Replies:
    1
    Views:
    227
    Yukihiro Matsumoto
    Feb 11, 2005
  3. Oliver Peng
    Replies:
    5
    Views:
    193
    Robert Klemme
    Mar 5, 2008
  4. Bezan Kapadia
    Replies:
    15
    Views:
    323
    Brian Candler
    Feb 16, 2009
  5. Mrmaster Mrmaster
    Replies:
    6
    Views:
    168
    Mrmaster Mrmaster
    Aug 10, 2009
Loading...

Share This Page