what is "stack level too deep (SystemStackError)" error

Discussion in 'Ruby' started by Mrmaster Mrmaster, Aug 8, 2009.

  1. Hi,

    I've created a binary search using code from wiki and when i run it i
    get there error stated below. I'm only using 10 entries so i'm not sure
    why it would give me that error. How can I modify my code to handle 100k
    entries?

    test.rb:14:in `binSearch': stack level too deep (SystemStackError)
    from test.rb:14:in `binSearch'
    from test.rb:20





    Here is my code:

    array = [1, 2, 3, 4, 5, 6, 7, 8, 9 , 10 , 11, 12, 13, 14, 15]
    target = 6
    left = 0
    right = (array.length)


    def binSearch(left, right, target, array)
    middle = left + ((right - left) / 2)
    if array[middle] == target then
    puts target
    elsif array[middle] > target then
    return binSearch(left, middle, target, array)
    elsif array[middle] < target then
    return binSearch(middle, right, target, array)
    else
    puts "Target does not exist"
    end
    end

    binSearch(left, right, target, array)
    --
    Posted via http://www.ruby-forum.com/.
     
    Mrmaster Mrmaster, Aug 8, 2009
    #1
    1. Advertising

  2. Mrmaster Mrmaster

    pharrington Guest

    On Aug 7, 7:52 pm, Mrmaster Mrmaster <> wrote:
    > Hi,
    >
    > I've created a binary search using code from wiki and when i run it i
    > get there error stated below. I'm only using 10 entries so i'm not sure
    > why it would give me that error. How can I modify my code to handle 100k
    > entries?
    >
    > test.rb:14:in `binSearch': stack level too deep (SystemStackError)
    >   from test.rb:14:in `binSearch'
    >   from test.rb:20
    >
    > Here is my code:
    >
    > array = [1, 2, 3, 4, 5, 6, 7, 8, 9 , 10 , 11, 12, 13, 14, 15]
    > target = 6
    > left = 0
    > right = (array.length)
    >
    > def binSearch(left, right, target, array)
    >   middle = left + ((right - left) / 2)
    >   if array[middle] == target then
    >     puts target
    >   elsif array[middle] > target then
    >     return binSearch(left, middle, target, array)
    >   elsif array[middle] < target then
    >     return binSearch(middle, right, target, array)
    >   else
    >     puts "Target does not exist"
    >   end
    > end
    >
    > binSearch(left, right, target, array)
    > --
    > Posted viahttp://www.ruby-forum.com/.


    When coding recursively, you *always* need to test for the exit
    condition first. With searches, this means ensuring your result set
    isn't empty before continuing. If your code still loops endlessly
    after doing this, it helps to print the search set each step of the
    way to see exactly whats going wrong.

    (in this case your set is actually the bounds passed to the method,
    not the array itself ***)
     
    pharrington, Aug 8, 2009
    #2
    1. Advertising

  3. pharrington wrote:
    > On Aug 7, 7:52�pm, Mrmaster Mrmaster <> wrote:
    >>
    >> � � puts target
    >> --
    >> Posted viahttp://www.ruby-forum.com/.

    >
    > When coding recursively, you *always* need to test for the exit
    > condition first. With searches, this means ensuring your result set
    > isn't empty before continuing. If your code still loops endlessly
    > after doing this, it helps to print the search set each step of the
    > way to see exactly whats going wrong.
    >
    > (in this case your set is actually the bounds passed to the method,
    > not the array itself ***)


    When I use 6 it gave me the answer but when I tried 20 as the target i
    received that answer. Wouldn't my exist be the either it found or else
    it didn't?

    I'm sorry but i don't know what you mean by your statement:

    >(in this case your set is actually the bounds passed to the method,
    > not the array itself ***)

    --
    Posted via http://www.ruby-forum.com/.
     
    Mrmaster Mrmaster, Aug 8, 2009
    #3
  4. Mrmaster Mrmaster

    pharrington Guest

    On Aug 7, 9:04 pm, Mrmaster Mrmaster <> wrote:
    > pharrington wrote:
    >
    > > When coding recursively, you *always* need to test for the exit
    > > condition first. With searches, this means ensuring your result set
    > > isn't empty before continuing. If your code still loops endlessly
    > > after doing this, it helps to print the search set each step of the
    > > way to see exactly whats going wrong.

    >
    > > (in this case your set is actually the bounds passed to the method,
    > > not the array itself ***)

    >
    > When I use 6 it gave me the answer but when I tried 20 as the target i
    > received that answer. Wouldn't my exist be the either it found or else
    > it didn't?
    >


    Well, what does "didn't find it" mean? Think about what a binary
    search is: take a bunch of sorted objects, check if what you're
    looking for is in the middle; if not divide that list in two and then
    search on the appropriate half. The set gets smaller and smaller (like
    little Russian dolls) until either you've found the thing or there's
    nothing left. Thus, "didn't find it" means that there's nothing left
    to search.

    > I'm sorry but i don't know what you mean by your statement:
    >
    > >(in this case your set is actually the bounds passed to the method,
    > > not the array itself ***)

    >
    > --
    > Posted viahttp://www.ruby-forum.com/.


    The... more straight-forward? naive? way to do this is to actually
    create another list that's half of the original list, can search
    through that. When doing that, you just check of the list itself is
    empty. In this case, you're changing array bounds to "create" a new
    list. So instead of checking if the array is empty, check to see if
    nothing can fit within the bounds.
     
    pharrington, Aug 8, 2009
    #4
  5. Mrmaster Mrmaster

    Josh Cheek Guest

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

    On Fri, Aug 7, 2009 at 6:52 PM, Mrmaster Mrmaster <>wrote:

    > Hi,
    >
    > I've created a binary search using code from wiki and when i run it i
    > get there error stated below. I'm only using 10 entries so i'm not sure
    > why it would give me that error. How can I modify my code to handle 100k
    > entries?
    >
    > test.rb:14:in `binSearch': stack level too deep (SystemStackError)
    > from test.rb:14:in `binSearch'
    > from test.rb:20
    >
    >
    >
    >
    >
    > Here is my code:
    >
    > array = [1, 2, 3, 4, 5, 6, 7, 8, 9 , 10 , 11, 12, 13, 14, 15]
    > target = 6
    > left = 0
    > right = (array.length)
    >
    >
    > def binSearch(left, right, target, array)
    > middle = left + ((right - left) / 2)
    > if array[middle] == target then
    > puts target
    > elsif array[middle] > target then
    > return binSearch(left, middle, target, array)
    > elsif array[middle] < target then
    > return binSearch(middle, right, target, array)
    > else
    > puts "Target does not exist"
    > end
    > end
    >
    > binSearch(left, right, target, array)
    > --
    > Posted via http://www.ruby-forum.com/.
    >
    >

    Hi, you have two issues with your algorithm, that I see. Here is what I
    would do http://pastie.org/576485 it explains what the two issues are, shows
    how I would change the code to fix them, as well as a few other small
    changes to make the code more usable, then runs through a few tests to make
    sure that it is doing what we think it is doing.

    In some browsers, pastie seems to word wrap, so if it does that for you, you
    should probably c&p it into your text editor for reading.
     
    Josh Cheek, Aug 8, 2009
    #5
  6. It looks like when the search gets to the right edge, there is nothing
    to stop it repeating itself infinitely - which of course blows the
    stack. Nothing is noticing that you are only looking at one element and
    you did that last time.

    Also I question whether right is array.length rather than array.length -
    1 since the index starts at 0.
    --
    Posted via http://www.ruby-forum.com/.
     
    Mike Stephens, Aug 10, 2009
    #6
  7. Mike Stephens wrote:
    > It looks like when the search gets to the right edge, there is nothing
    > to stop it repeating itself infinitely - which of course blows the
    > stack. Nothing is noticing that you are only looking at one element and
    > you did that last time.
    >
    > Also I question whether right is array.length rather than array.length -
    > 1 since the index starts at 0.


    Thank you all for the clarification on the code. I can't believe I
    missed the exit and forgot about subtracting 1 from length ><.
    --
    Posted via http://www.ruby-forum.com/.
     
    Mrmaster Mrmaster, Aug 10, 2009
    #7
    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. hfk0
    Replies:
    2
    Views:
    21,745
  2. JavaQueries
    Replies:
    1
    Views:
    3,765
    John C. Bollinger
    Mar 1, 2005
  3. Balaji
    Replies:
    3
    Views:
    10,192
  4. Bishop
    Replies:
    1
    Views:
    825
    Bishop
    Feb 24, 2007
  5. Jesper Olsen
    Replies:
    7
    Views:
    619
    Van Jacques
    Jan 16, 2004
Loading...

Share This Page