Using Recursion to Add

[Hexus0]

Hey everyone, well I'm like 5/6s complete with my assignment (out of 6 methods, I've completed 5), all on recursion. I'm having a little trouble with this last one though, I have to recursively add the left side of an array, then add the middle element, then add the right side, "divide and conquer" basically.

This is what I have so far (sorry if its a little messy,the copy/paste kind of messed it up):

public static int sum(int a[], int lf, int rt) { 
  int sum = 0;
  int left = 0;
  int right = 0;
  if(a.length == 0) {
      sum = 0;
   } else if(lf > rt) {
	//
   } else {
	if(lf < rt) {
		System.out.println("lf " + lf + " right " + rt);
		int mid = (lf + rt) / 2;
		System.out.println(mid);
		left = left + a[sum(a, lf, mid-1)];
		right = right + a[sum(a, mid+1, rt)];
		sum = left +  mid + right;		
	}
		
  }
  return sum;
}

Its throwing an array out of bounds error, I'm assuming because its trying to do a[5] (I'm using a 5 element array, so the highest is a[4]).

Thanks!

 

[mikeblas]

Why are you indexing a[] by the result of the sum() call? I would have expected sum() to compute a partial sum, not an index into the array.

 

[Hexus0]

You're right, I didn't realize that I'm trying to index a sum, I've been use to using find max and using that as an index. I'll edit it and give it a try, thanks for pointing that out.

Edit: So I've been trying but I'm shooting in the dark here, this is my update.

public static int sum(int a[], int lf, int rt) { 
		int sum = 0;
		int left = 0;
		int right = 0;
		int middleValue = a[(lf + rt) / 2];
		int mid = (lf + rt) / 2;
		if(a.length == 0) {
			sum = 0;
		} else if (lf > rt) {
			///
		} else {
			left = left + sum(a, lf, mid-1);
			right = right + sum(a, mid+1, rt);		
		}
		
		sum = left +  middleValue + right;
		
		return sum;
	}

Any ideas? I'm kind of stumped...

 

[Arainach]

Disclaimer: I'm a C++ guy, not a java guy.

If I had to guess, I'd say it was down to calling sum(a, 0, 0), which calls sum(a, 0, -1) and such until middleValue is a[some negative number].

A few other points:

• There's no need to calculate (lf + rt) / 2 twice. Calculate mid and then just use a[mid] rather than middleValue.
• Unless it's some weird java quirk, I see no reason to set left and right to 0 and then do left = left +.sum. Just do left = sum(...)
• The sum variable isn't just unnecessary, it's very bad form. Don't have functions and variables named the same thing. Makes the code horrible to read. Just use return left + a[mid] + right
• If a.length has any meaning at all, then your a.length check seems woefully insufficient, as it'll always return the length of the original string, NOT the length of the portion you're currently working on.

Hopefully that will point you in the right direction a bit.

 

[mikeblas]

"Very bad form" ? "Horrible to read" ? I think these aren't helpful criticisms, and maybe that's debatable -- but they're certainly over-stated.

To fix things like this yourself, Hexus0, you need to start debugging. What happens as you step through your code? How do the values of the variables differ from what you expect them to be?

You're telling us you're kind of stumped, but you don't tell us why. Does your program not compile? Fail at runtime, with some error? What error? Fail at runtime with incorrect results? What input do you give, and what output do you get, and what do you expect instead?

How are you calling this function? What parameters are you passing it?

You're not handling the case where lf == rt, or the case where lf < rt. What happens then?

 

[:LJ:]

Just as a small hint as to one thing which might be going wrong....

int middleValue = a[(lf + rt) / 2];

What do you think might happen if (lf + rt) = 3?

 

[LuminaryJanitor]

You're not handling the case where lf == rt, or the case where lf < rt. What happens then?

I think it's fine. When lf == rt, the current call generates the value you want (that is, a[(lf+rt)/2] == a[lf] == a[rt] ), and both recursive calls will hit base cases - sum(a,lf,rt-1) and sum(a,lf+1,rt) are guaranteed to satisfy the lf > rt condition. So as long as the base case is done right, lf == rt can be handled the same way as your typical lf < rt case, with both taken care of in the last else block.

Any ideas? I'm kind of stumped...

One thing I need to know first is your initial call to the function - without knowing how it's being used, I can't know for sure whether it's working right.

In recursive functions like this one, the user should only need to supply a[], so it's a good idea to put this first call in a separate function:

public static int sum(int[] a)
{   return sumAux(a, <initial lf>, <initial rt>); }

private static int sumAux(int[] a, int lf, int rt)
<your code here>

If you could fill that in, I should be able to help you out.


EDIT:

What do you think might happen if (lf + rt) = 3?

I hope you're not suggesting that 3 / 2 = 1.5... This is integer division, remember?

 

[mikeblas]

What do you think might happen if (lf + rt) = 3?

What's more interesting is if lf + rt > INT_MAX.

I think it's fine. When lf == rt, the current call generates the value you want (that is, a[(lf+rt)/2] == a[lf] == a[rt] ), and both recursive calls will hit base cases - sum(a,lf,rt-1) and sum(a,lf+1,rt) are guaranteed to satisfy the lf > rt condition. So as long as the base case is done right, lf == rt can be handled the same way as your typical lf < rt case, with both taken care of in the last else block.

It's far from fine. As is, the guarantee only holds if they don't throw an out-of-bounds exception. What if lf == rt == 0 ?

If lf == 3, and rt == 3, we should just return a[3].

The code Hexus0 has written doesn't do that because he doesn't handle the lf == rt case. Instead, he keeps recursing and ends up returning a[3] + a[4] + a[4].

What if lf == rt == a.length-1 ?

 

[:LJ:]

I hope you're not suggesting that 3 / 2 = 1.5... This is integer division, remember?

Purrlease, give me some credit. Point is, you end up selecting the same middle value as when lf+rt = 2, which strikes me as not what he wanted to do.

Of course, I did look at this in a hurry, so it's entirely possible I've missed the point.

 

[LuminaryJanitor]

It's far from fine. As is, the guarantee only holds if they don't throw an out-of-bounds exception. What if lf == rt == 0 ?

If lf == 3, and rt == 3, we should just return a[3].

The code Hexus0 has written doesn't do that because he doesn't handle the lf == rt case. Instead, he keeps recursing and ends up returning a[3] + a[4] + a[4].

What if lf == rt == a.length-1 ?

Still don't see the problem...

I'm assuming an initial call of sum(a,0,a.length-1) (i.e. lf and rt are the first and last indices). The base case, where lf > rt, should return 0.

Say lf == rt == x. Then we return sum(a,x,x-1) + a[x] + sum(a,x+1,x). Both recursive calls are base cases and return 0, so the return from this call is a[x].

EDIT: Oops, I think I see what you're getting at now... I thought that the "else if (lf > rt)" block was yet to be coded, not left empty intentionally. That's certainly going to mess things up... I still disagree on the need for a separate lf==rt case, though.

Purrlease, give me some credit. Point is, you end up selecting the same middle value as when lf+rt = 2, which strikes me as not what he wanted to do.

Sorry, no offence intended .

It doesn't matter where you split the index range. Take any value, plus all values to the left, plus all values to the right, and you get the total sum, regardless of where the value is.

With divide and conquer methods like this, the choice can have performance implications if the runtime for each recursive call depends on the size of the input (which it doesn't in this case), but I don't think it'll ever affect functionality.

 

[mikeblas]

Say lf == rt == x. Then we return sum(a,x,x-1) + a[x] + sum(a,x+1,x). Both recursive calls are base cases and return 0, so the return from this call is a[x].

What do you believe to be the "base case"?

EDIT: Oops, I think I see what you're getting at now... I thought that the "else if (lf > rt)" block was yet to be coded, not left empty intentionally. That's certainly going to mess things up... I still disagree on the need for a separate lf==rt case, though.

What I'm getting at is the code is completely broken. It's possible to fix it without an explicit lf == rt case, but to me that's precisely the base case:

if ( lf == rt )
   return a[lf];   // sum of one element is that element itself
else
{
   // calculate the midpoint,
   // sum the left of the midpoint
   // and the right of the midpoint, ...
}

The code we're looking at from Hexus is recursing in the base case, which fails: it does unnecessary work, and gets unexpected results. Again, a few moments in a debugger with this code would show Hexus all of the problems we've found for him.

It doesn't matter where you split the index range.

Right. Rounding the split point doesn't matter here. The bug is letting the math to compute the split point overflow.

 

[Mr_Superstar]

What's more interesting is if lf + rt > INT_MAX.

This is a very good point that no one has yet replied too. If lf + rt > INT_MAX (assuming signed int's, as in java), the result will overflow and return a negative value. Then, dividing by two will still result in a negative number. Using this as an array index will cause an ArrayIndexOutOfBoundsException.

The better way to select the midpoint is the following:

int mid = lf + ((rt - lf) / 2)

 

[mikeblas]

Or does Java throw an exception when integer math overflows?

 

[LuminaryJanitor]

What do you believe to be the "base case"?

Given initial arguments of 0 and length-1, I took it to be when the specified range is empty, i.e. when lf > rt. I thought it was more suitable than the one-element case, because it doesn't require special treatment of zero-length arrays.

What I'm getting at is the code is completely broken. It's possible to fix it without an explicit lf == rt case, but to me that's precisely the base case

It looks to me like returning 0 from the lf>rt case will fix it completely. When you get down to one element, the range will be empty on both subsequent recursive calls and they'll return 0, leaving you with just the element.

It shouldn't even go out of bounds in the boundary cases you mentioned - sum(a,0,0) will call sum(a,0,-1), but (0-1)/2 = 0, and sum(a,a.length-1,a.length-1) will call sum(a,a.length,a.length-1), but (a.length+a.length-1)/2 = a.length-1. I doubt it works out like this by design, though...

 

[Mr_Superstar]

Or does Java throw an exception when integer math overflows?

Nope, it just overflows...