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 4 of 4

Thread: Recursion, arrays and greatest common divisor

  1. #1
    Junior Member
    Join Date
    Dec 2011
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Recursion, arrays and greatest common divisor

    I'm trying to write a method that receives an int array and returns true if all of the array's integers are "non-relative"( not sure if that's how you say it), by non relative I mean that their greatest common divisor is 1
    the method will return false otherwise.

    This is my code (including the GCD calculation method):
    public static int gcd(int m, int n)
    {
      if (m%n==0)
      {
        return n;
      }
       else
       {
          return gcd(n,m%n);
       }
    }
    private static int i=0;
    public static boolean checkGCD(int[] values)
    {
      if(i < values.length-1)
      {
        if (gcd(values[i],values[i++])!=1)
        {
         return false;
        }
        return checkGCD(values);
      }
      return true;
    }

    I'm pretty sure the GCD method is correct which leaves me with the second one..
    I've tried writing it on paper, I've tried debugging it. I still can't figure it out.
    could anyone please shed some light on this for me?

    Thanks,

    Gal


  2. #2
    Forum VIP
    Join Date
    Jun 2011
    Posts
    308
    My Mood
    Bored
    Thanks
    45
    Thanked 86 Times in 72 Posts
    Blog Entries
    4

    Default Re: Recursion, arrays and greatest common divisor

    What you need is a for loop. They look like this:

    for (int i = 0; i < myArray.length; i++) {
         doSomething(myArray[i]);
    }

    Use a for loop to iterate through all the values of the array. I suspect you want to check each combination of numbers. To do this, you will need a nested for loop ie, a for loop inside a for loop. This will start with the first item in the array and check it against every other item. When it has done checking every pair of numbers for GCD starting from the first, it moves on to the second.

  3. #3
    Junior Member
    Join Date
    Dec 2011
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Recursion, arrays and greatest common divisor

    Sorry. I thought I had mentioned it in the main post.
    Loops are out of the question, recursion only here.
    thanks for your input though.

  4. #4
    Forum VIP
    Join Date
    Jun 2011
    Posts
    308
    My Mood
    Bored
    Thanks
    45
    Thanked 86 Times in 72 Posts
    Blog Entries
    4

    Default Re: Recursion, arrays and greatest common divisor

    Why's that? Is it the requirements for an assignment or something? I cannot just give you the answer here because it violates this forums rules on spoon feeding answers. The only hint I can give you is that you should put a break point in the checkGCD(int[] values) method and watch what happens to the values parameter each time the method is called. Consider how you need to alter the parameters so it will behave the same way the regular nested for loop would. If you haven't yet done so, I'd recommend writing a nested for loop solution so you can verify the output of the recursive one and compare them.

Similar Threads

  1. Recursion Help
    By WeaKeN in forum Algorithms & Recursion
    Replies: 10
    Last Post: May 27th, 2011, 08:17 AM
  2. [SOLVED] Recursion help
    By Actinistia in forum Java Theory & Questions
    Replies: 3
    Last Post: March 21st, 2011, 12:26 PM
  3. Recursion
    By javapenguin in forum Algorithms & Recursion
    Replies: 12
    Last Post: October 18th, 2010, 03:42 PM
  4. Recursion Help
    By vmr in forum Algorithms & Recursion
    Replies: 3
    Last Post: April 1st, 2010, 11:27 PM
  5. Recursion help
    By rhoruns in forum Algorithms & Recursion
    Replies: 4
    Last Post: January 8th, 2010, 10:50 PM