Results 1 to 9 of 9
  1. #1
    Falantar is offline Member
    Join Date
    Jan 2011
    Posts
    5
    Rep Power
    0

    Talking 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!

  2. #2
    Iron Lion is offline Senior Member
    Join Date
    Nov 2010
    Posts
    210
    Rep Power
    4

    Default

    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.

  3. #3
    Falantar is offline Member
    Join Date
    Jan 2011
    Posts
    5
    Rep Power
    0

    Default

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

  4. #4
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    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) {
                    ...
            }
    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?

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

    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);
            }
    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-

  5. #5
    Falantar is offline Member
    Join Date
    Jan 2011
    Posts
    5
    Rep Power
    0

    Default

    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.

  6. #6
    Falantar is offline Member
    Join Date
    Jan 2011
    Posts
    5
    Rep Power
    0

    Default

    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.

  7. #7
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    Quote Originally Posted by Falantar View Post
    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-

  8. #8
    Falantar is offline Member
    Join Date
    Jan 2011
    Posts
    5
    Rep Power
    0

    Default

    Quote Originally Posted by gcalvin View Post
    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.

  9. #9
    subith86 is offline Senior Member
    Join Date
    Jan 2011
    Location
    Bangalore, India
    Posts
    102
    Rep Power
    0

    Default

    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

  1. Problem with arrays
    By Viper in forum New To Java
    Replies: 7
    Last Post: 10-07-2010, 03:49 PM
  2. recursive method problem
    By melody in forum New To Java
    Replies: 1
    Last Post: 10-29-2009, 08:15 AM
  3. Java Recursive method problem
    By kj2009 in forum Advanced Java
    Replies: 2
    Last Post: 02-25-2009, 04:19 PM
  4. Recursive File List - Help me problem solve please
    By caps_lock in forum New To Java
    Replies: 17
    Last Post: 01-14-2009, 07:44 PM
  5. problem with recursive binary search program
    By imran_khan in forum New To Java
    Replies: 3
    Last Post: 08-02-2007, 04:08 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •