# Problem with recursive use of arrays.

• 01-24-2011, 09:34 PM
Falantar
Problem with recursive use of arrays.
Hey guys I'm new to this forum. I'm a student studying comp sci in university and I'm in my 2nd year. I currently have a problem where I need to create a recursive method that accepts an array of positive integers and checks if there is at least one value that is the sum of any 2 values that appear previously.

Example: Array[1,2,5,3,6] would be true because 1+5 = 6.
Array[1,6,2,5,4] would be false.

I'm not asking for code, only suggestions on how I should go about doing it. I'm having a hard time wrapping my brain around recursion, though I understand the concept, I have difficulty solving problems using recursive functions.

• 01-24-2011, 10:24 PM
Iron Lion
Judging by your syntax (Array[1,2,5,3,6]) I'm assuming that you're using JavaScript rather than Java. The two languages are completely unrelated.

Looks like what you want to do is have a method/function that accepts an array, and loops through each number except the last to see if it can be added to any other number to give the last number. If it does, it returns true; otherwise, it calls itself with the same array minus the last element. When the array is 1 element long, it returns false.
• 01-24-2011, 10:33 PM
Falantar
No I'm using java, I just wasn't being syntactically correct. Going by your method, how do you propose I make the function call itself and pass the array minus the last element? Would I have to recreate the same array minus the last element?

Also shouldn't the stopping case be if the array is of length 2 instead of 1 (since I need the sum of 2 previous integers therefore needing the array to be 3 total length).
• 01-24-2011, 10:37 PM
gcalvin
It's not obvious to me that recursion is a great approach to this problem, but that's not really all that unusual for classroom exercises teaching recursion -- very often recursion is not really the best approach, but they want you to do it that way anyway.

So we know that our method is going to take an array of ints as a parameter, and is going to return a boolean.
Code:

```        public boolean hasSum(int[] testArray) {                 ...         }```
Next we want to think about the base cases -- the easy-to-identify situations that let us return a result right away. One base case is if the array has fewer than three elements -- if we don't have at least three elements, we can't have two of them summing to a third, can we?

Code:

```        public boolean hasSum(int[] testArray) {                 if (testArray.length < 3) return false;         }```
Now it gets tricky. Basically, we want to do a simple subset of our testing. If we find a sum, we can return true, and if we don't, we want to take one element off the array, and pass the smaller array to another instance of our method. Eventually, one of these methods will either return true or have an array with a length less than three and return false. I'll leave you to work out the details of that, but you'll certainly want to do something like this:

Code:

```        public boolean hasSum(int[] testArray) {                 if (testArray.length < 3) return false;                 int[] smallerArray = new int[testArray.length - 1];                 // code that checks for a sum while filling smallerArray                 // with either the first or last element removed from testArray                 if (<you found a sum>) return true;                 return hasSum(smallerArray);         }```
Now that test code will probably involve a pair of nested loops. I guess the simplest thing is to check if you can sum to the last element of the array, but you could also pull off the first element and see if you can make it work in a sum. Hope that makes sense.

-Gary-
• 01-24-2011, 10:59 PM
Falantar
Thanks, i'll work some more on it tonight and see what I can come up with. That's about the direction I was going so it's good to know I'm not crazy.
• 01-26-2011, 12:05 AM
Falantar
Thanks again GCalvin! I was able to solve it with your help :) Just a couple of nested for loops to check the condition and another separate for loop to recreate the array was all I was really missing. The recursive call at the end too instead of in the middle like I was trying to do lol. I wasn't able to find a way to integrate the recreation of the new array into the for loops that check for the condition though but that's no big deal.
• 01-26-2011, 01:43 AM
gcalvin
Quote:

Originally Posted by Falantar
Thanks again GCalvin! I was able to solve it with your help :) Just a couple of nested for loops to check the condition and another separate for loop to recreate the array was all I was really missing. The recursive call at the end too instead of in the middle like I was trying to do lol. I wasn't able to find a way to integrate the recreation of the new array into the for loops that check for the condition though but that's no big deal.

Glad you got it working. Now my guess is that a slight modification of your nested-loop code (one more outer loop?) could solve the whole thing without resorting to recursion at all. And by doing this recursively, we're creating all these copies of the array and stacking up a bunch of method calls needlessly. Am I right?

-Gary-
• 01-26-2011, 04:13 AM
Falantar
Quote:

Originally Posted by gcalvin
Glad you got it working. Now my guess is that a slight modification of your nested-loop code (one more outer loop?) could solve the whole thing without resorting to recursion at all. And by doing this recursively, we're creating all these copies of the array and stacking up a bunch of method calls needlessly. Am I right?

-Gary-

Yessir you are preaching to the choir, but this is a homework assignment and I guess the professor wanted to make us over-complicate a solution using recursion lol.
• 01-26-2011, 04:23 AM
subith86
Hi,

Just now i posted an answer for recursion.
First of all read my post @
http://www.java-forums.org/new-java/...tml#post172974

I have given a picturized description of how recursion works.