• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

recursion stack overflow error when array has more than 3 elements

 
Greenhorn
Posts: 10
Mac Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm working on a recursion problem that I thought was going okay. The problem is to find the largest number in an array using recursion.
I got something working...but it only works if there are 3 or fewer elements in the array. As soon as I add a fourth (or more), I get the stack overflow error. This array is far far too small to be using up all my memory...right? or is my recursion just wildly off base?

I really don't understand why 4+ elements triggers this; I've been trying to figure it out for 2 days. Can anyone help?

Here is the code... this is working as-is. But if I add one more int to int[]a, then the stack overflow occurs.

 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Try going through it by hand. I suggest you make that into object‑oriented code first, by passing the args parameter to the constructor

[campbell@computer java]$ java Recursion 1 2 69
The biggest number is 69

So far, so good. Now go through it by hand. Work out the arguments passed, and what first last and mid are in the first recursive call. go through all the calls and see whether you get to your base case (first == last) for every route.
Now repeat the procedure with
]

[campbell@computer java]$ java Recursion 1 2 69 4
Exception in thread Main etc etc

Notice that using args allows you to pass an array of any length and see what happens, without having to recompile every time.
See whether every path gives you the base case and stops the recursion. See whether you ever reach a state where (first > last)
 
brenda flire
Greenhorn
Posts: 10
Mac Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for the hints, Ritchie. I will work on it. However, I think my problem is that my brain just sunk into a big black hole on this one. I've tried a few other recursion problems that worked for all the cases I could come up with. I'm pretty sure they were more complex than this one, too.

For this one... I have about 8 double-sided notebook pages filled with me doing this particular problem by hand (that's part of what took 2 days). I've had many many iterations of the code and in fact I DID come up with a case where first > last. I thought I handled it but it made no difference regarding the size of the array...and I did that by hand over and over too. At some point I gave up on all those avenues because the changes I was making and the traces I was doing weren't showing anything different for 4 elements vs. 3 elements. And by "weren't showing" I mean, "I wasn't seeing"...they could have been showing me the issue and I just didn't get it.

I really think I've just confused myself into a corner and now I have a blind spot with this particular problem.

Still, I'll go back and try it by hand all over again. Maybe today my brain will click into it.
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Try some print statements, printing the values of first last and mid after line 15 (your original version)
Also put a static int count field in your class. Add the following to the beginning of the biggest methodway you won't have 1000000 printouts to read.

I think you will find an error in a few minutes like that.
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Have you found it yet? this is what I got when I tried it, and it only took about two minutes.

[campbell@computer java]$ java Recursion 1 2 69 4
first = 0, mid = 1, last = 3
first = 0, mid = 0, last = 1
first = 2, mid = 1, last = 3
first = 2, mid = 0, last = 1
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
first = 2, mid = 0, last = 0
Exception in thread "main" java.lang.RuntimeException: Taking too long.

Something is calling the recursion with the left argument greater than the right. You can see you are always getting the same call. It will never reach the base case.
 
brenda flire
Greenhorn
Posts: 10
Mac Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sorry, didn't get a chance to follow up on this till now. Actually, I didn't do what you suggested today, but I have done that in my attempts to figure out this problem before I posted here. And yes, I did get the very same output. But apparently I don't GET it, because everything I tried to resolve the issue either gave me the same result or caused some other type of exception.

Anyway, I am just getting time to look at this again, hopefully I'll be able to update with better news soon.
 
brenda flire
Greenhorn
Posts: 10
Mac Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote: It will never reach the base case.



This is what doesn't make sense to me. I *do* reach the base case when the array has 3 or fewer items in it. At least, I thought I was hitting it, because the method worked (and by that I mean it gave the results I wanted to get). But once my array hits 4 elements, I don't reach the base case. Maybe I am focusing too much on the wrong thing (i.e., this 3 vs greater-than-3 problem).

Also, sorry I didn't put in what stuff I've tried and what other conclusions I've reached, it's just that I had days and pages of attempts and couldn't assimilate everything I'd tried to post it all here...and a good portion was mush in my head by that point too.

Ok, back to it!
 
brenda flire
Greenhorn
Posts: 10
Mac Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hallelujah! I think it's working. I have a bit more checking to do, but it seems to be working so far.

The code I originally posted had: int mid = (first+(last-first))/2;

Now I have: int mid = (first+last)/2;
and all seems well. Still checking, though.

I know I changed to (first +(last-first))/2 for some reason. I think I thought it might fix some *other* issue I was having, and I never removed this "fix". Definitely a blind spot. I really knew it had to be something to do with this yet I couldn't see it for all that time. I even knew that exact statement had a problem and had modified it a few times; but then I switched to writing cases to deal with the nonsense it had the potential to return. Of course, that was a disaster too.

I was determined to figure out this issue on my own, but I ended up just losing myself in myriads of pseudocode, code, attempted traces...and then confusing which parts worked and which parts didn't.

Any tips for how to avoid this? I did put the problem aside (I started this on Sunday) every time I realized I was getting hopelessly confused. Then I'd come back the next day and try again and immediately slip into a brain fog .

I guess next time I'll ask for help earlier. Or, maybe I will stop trying to fix code when I should really be sleeping .
Thanks for the nudges, Ritchie!
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It had to be an arithmetical error, didn't it. (first + (last - first))/2 reduces to last / 2. When you use mid + 1, you will eventually start a recursion where the left argument is greater than the right argument. What you want is
first + (last - first) / 2

Well done finding it
 
permaculture is largely about replacing oil with people. And one tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic