posted 4 years ago

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.

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.

Campbell Ritchie

Marshal

Posts: 56546

172

posted 4 years ago

Try going through it by hand. I suggest you make that into object‑oriented code first, by passing the args parameter to the constructor

Now repeat the procedure with

]

See whether every path gives you the base case and stops the recursion. See whether you ever reach a state where (first > last)

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.[campbell@computer java]$ java Recursion 1 2 69

The biggest number is 69

Now repeat the procedure with

]

Notice that using args allows you to pass an array of any length and see what happens, without having to recompile every time.[campbell@computer java]$ java Recursion 1 2 69 4

Exception in thread Main etc etc

See whether every path gives you the base case and stops the recursion. See whether you ever reach a state where (first > last)

posted 4 years ago

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.

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: 56546

172

posted 4 years ago

Try some print statements, printing the values of first last and mid after line 15 (your original version)

Also put a

I think you will find an error in a few minutes like that.

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: 56546

172

posted 4 years ago

Have you found it yet? this is what I got when I tried it, and it only took about two minutes.

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.[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.

posted 4 years ago

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.

Anyway, I am just getting time to look at this again, hopefully I'll be able to update with better news soon.

posted 4 years ago

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!

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!

posted 4 years ago

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!

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: 56546

172