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


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: Need help with Java recursion problem!

  1. #1
    Junior Member
    Join Date
    Apr 2012
    Posts
    13
    My Mood
    Cheerful
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,607
    My Mood
    Hungover
    Thanks
    145
    Thanked 658 Times in 563 Posts

    Default 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
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Junior Member
    Join Date
    Apr 2012
    Posts
    13
    My Mood
    Cheerful
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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!
    Last edited by eyesackery; June 5th, 2012 at 09:15 AM.

Similar Threads

  1. How do you employ recursion into a Java Boggle program?
    By techcom0 in forum Java Theory & Questions
    Replies: 2
    Last Post: October 3rd, 2011, 09:13 AM
  2. Recursion for N Queens problem
    By dubois.ford in forum Algorithms & Recursion
    Replies: 0
    Last Post: February 23rd, 2011, 09:46 PM
  3. recursion problem, please help
    By nil in forum What's Wrong With My Code?
    Replies: 2
    Last Post: October 18th, 2010, 01:59 PM
  4. New Recursion problem need lil help
    By Delstateprogramer in forum Algorithms & Recursion
    Replies: 21
    Last Post: July 8th, 2010, 07:35 PM
  5. Recursion Problem Need Help ASAP
    By Delstateprogramer in forum Algorithms & Recursion
    Replies: 6
    Last Post: June 26th, 2010, 09:36 PM