# Recursion, arrays and greatest common divisor

• January 14th, 2012, 08:21 PM
GalBenH
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):
Code :

```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
• January 14th, 2012, 09:15 PM
ChristopherLowe
Re: Recursion, arrays and greatest common divisor
What you need is a for loop. They look like this:

Code Java:

```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.
• January 14th, 2012, 09:19 PM
GalBenH
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.
• January 14th, 2012, 11:46 PM
ChristopherLowe
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.