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

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

On Wed, Sep 30, 2009 at 3:47 PM, Joshua M. [email protected] wrote:

end
(#{result_h})"

Thanks a lot for help
Josh

Posted via http://www.ruby-forum.com/.

Rewrite it to not be recursive.

Jason

Jason R. wrote:

On Wed, Sep 30, 2009 at 3:47 PM, Joshua M. [email protected] 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. :wink:
http://en.wikipedia.org/wiki/Tautology

On Sep 30, 2009, at 4:30 PM, Joshua M. wrote:

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. :wink:
http://en.wikipedia.org/wiki/Tautology

Or a problem from Project Euler… :wink:
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 B. http://agileconsultingllc.com
[email protected]

On Sep 30, 2009, at 3:47 PM, Joshua M. 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 W.

On Wed, Sep 30, 2009 at 4:56 PM, Joshua M. [email protected] wrote:

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

Or a problem from Project Euler… :wink:
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 B. http://agileconsultingllc.com
[email protected]

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.

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. :slight_smile: 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. :slight_smile:

On Sep 30, 2009, at 5:02 PM, Jason R. wrote:

it uses a constant amount of space (i.e., no recursion at all, just

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 B. http://agileconsultingllc.com
[email protected]

On Wednesday 30 September 2009 04:17:31 pm Rob B. 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.

On Wed, Sep 30, 2009 at 1:55 PM, Jason R.
[email protected]wrote:

Rewrite it to not be recursive.

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

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

end
(#{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.

On Wed, Sep 30, 2009 at 3:56 PM, Joshua M. [email protected] wrote:

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

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

On Wed, Sep 30, 2009 at 1:55 PM, Jason R. [email protected]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

On Thursday 01 October 2009 05:05:13 am Simon K. wrote:

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

On Wed, Sep 30, 2009 at 1:55 PM, Jason R.
[email protected]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.

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs