[prev in list] [next in list] [prev in thread] [next in thread] 

List:       ruby-talk
Subject:    Re: SystemStackError: stack level too deep > how make it deeper?
From:       Ken Bloom <kbloom () gmail ! com>
Date:       2009-09-30 23:08:30
Message-ID: pan.2009.09.30.22.23.47 () gmail ! com
[Download RAW message or body]

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/


[prev in list] [next in list] [prev in thread] [next in thread]