Results 1 to 9 of 9
 01242011, 09:34 PM #1Member
 Join Date
 Jan 2011
 Posts
 5
 Rep Power
 0
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.
Thanks in advance!
 01242011, 10:24 PM #2Senior Member
 Join Date
 Nov 2010
 Posts
 210
 Rep Power
 5
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.
 01242011, 10:33 PM #3Member
 Join Date
 Jan 2011
 Posts
 5
 Rep Power
 0
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).
 01242011, 10:37 PM #4Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 5
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.
Java Code:public boolean hasSum(int[] testArray) { ... }
Java Code:public boolean hasSum(int[] testArray) { if (testArray.length < 3) return false; }
Java 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); }
Gary
 01242011, 10:59 PM #5Member
 Join Date
 Jan 2011
 Posts
 5
 Rep Power
 0
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.
 01262011, 12:05 AM #6Member
 Join Date
 Jan 2011
 Posts
 5
 Rep Power
 0
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.
 01262011, 01:43 AM #7Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 5
Glad you got it working. Now my guess is that a slight modification of your nestedloop 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
 01262011, 04:13 AM #8Member
 Join Date
 Jan 2011
 Posts
 5
 Rep Power
 0
 01262011, 04:23 AM #9Senior Member
 Join Date
 Jan 2011
 Location
 Bangalore, India
 Posts
 102
 Rep Power
 0
Hi,
Just now i posted an answer for recursion.
First of all read my post @
Recursive Edit Distance, 1 mistake.. help please
I have given a picturized description of how recursion works.
Make your concepts clear and then write your code.
Similar Threads

Problem with arrays
By Viper in forum New To JavaReplies: 7Last Post: 10072010, 02:49 PM 
recursive method problem
By melody in forum New To JavaReplies: 1Last Post: 10292009, 08:15 AM 
Java Recursive method problem
By kj2009 in forum Advanced JavaReplies: 2Last Post: 02252009, 04:19 PM 
Recursive File List  Help me problem solve please
By caps_lock in forum New To JavaReplies: 17Last Post: 01142009, 07:44 PM 
problem with recursive binary search program
By imran_khan in forum New To JavaReplies: 3Last Post: 08022007, 03:08 PM
Bookmarks