Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: Need help with Java recursion problem!

1. ## Need help with Java recursion problem!

Hey guys, have been struggling with a recursion homework problem. Would be very appreciative if someone could give me a nudge in the right direction, or a hint.

The Question (The algorithm has to use recursion, no loops allowed.

////////////////////////////// PROBLEM STATEMENT //////////////////////////////
// Given an array of ints, is it possible to choose a group of some of the
// ints, such that the group sums to the given target with this additional
// constraint: If a value in the array is chosen to be in the group, the
// value immediately following it in the array must not be chosen. (No loops
// needed.)
// (0, {2, 5, 10, 4}, 12) -> true
// (0, {2, 5, 10, 4}, 14) -> false
// (0, {2, 5, 10, 4}, 7) -> false
//////////////////////////////////////////////////////////////////////////////////////

Thanks guys, got some really helpful feedback last night I posted a thread!

2. ## Re: Need help with Java recursion problem!

What have you tried? Where are you stuck? What part of this confuses you?

Recommended reading: Starting Writing a Program

3. ## Re: Need help with Java recursion problem!

Recursion on the whole has been difficult to understand, but I have been getting through a few easier problems and gaining understanding.

As far as this problem goes, I'll try to write the code I need to solve this one.

Based on the input of 0 {5, 10, 2, 2, 3, 3} 15 - which would yield true. (The first element being an index int).

``` // 'a' being the array, 'i' the index, 'sum' an int to store the total, 'n' being the expected result).

static void checkSum(int[] a, int i, int sum, int n)
{
int total = sum;                 //this will set total to the value passed to the method (starts at 0)
if ( i < a.length )                // if i is less than a.length (5)
{
total += a[i];                   // total is equal to total plus the value stored in element i
i += 2;                            // increment i by 2 to get the next value
checkSum(a, i, total, n);    // recur on this method passing the updated i int
}
else
if ( total == n )                  // if the problem is solved
System.out.print(true);
else
System.out.print(false);
}```

That works as long as the sum expects the method to only be run from the first element onwards, incrementing the index by 2 each time.

In {2, 5, 10, 4, 2} - 7, this wouldn't work considering the 5 and 2 would never be added together.

This is where I'm stuck!