# Recursive boolean

#### ZKR

##### Honorable
Hello, help needed again.
I have successfully written a method that accepts 2 integers and checks for a great common divider using a Euclidean algorithm.

Now I have to write a recursive method which accepts an array, and returns True if all numbers in the array are Coprime (dividable by '1' only and no greater number) with each other .
It is stated that no loops should be used.

From my understanding, the recursive "array checker" uses the 2 integers checker. How can I pass the "gcd" method the values each time, without a loop?

Code:
``````public static boolean checkGCD (int[] values)
{
boolean result = true;
int gcd;

gcd = GcdTester.gcd     // that "gcd" method accepts 2 ints, but how to pass them to it, incrementing each time
if (gcd != 1)
result = false;
else
GcdTester.checkGCD (values);

return (result);
}``````
Does it involves using a linked list somehow?

#### Sunius

##### Distinguished
Yea my bad The actual call of checkGCD should be:

Code:
``checkGCD(0, 1, array.Length, array)``
Code:
``checkGCD(array, 1, array.Length, array))``

#### PhilFrisbie

##### Distinguished

No, I don't think so, but you need to loop through the array. . .

#### Sunius

##### Distinguished
Something like this:
Code:
``````public static bool checkGCD(int g, int j, int n, int[] array)
{
if (g == 1)
return true;
else if (j == n)
return false;
else
return checkGCD(GcdTester.gcd(g, array[j]), j + 1, n, array);
}``````
You could call it with
Code:
``GcdTester(array, 1, n, array);``

#### ZKR

##### Honorable
The heading of `checkGCD` should be: public static boolean checkGCD (int[] values)
If it calls itself with method overloading passing the data you added ((int g, int j, int n, int[] array)) is it still considered recursive?

What should 'n' be assigned to?

When I assign it to values.length it only checks the first set of numbers and doesn`t progress.
How to make it progress through?

here`s my edited code:
Code:
``````public static boolean checkGCD (int[] values)
{
int n = values.length;
if (GcdTester.checkGCD(values, 1, n, values))
return true;
return false;
}

public static boolean checkGCD(int g, int j, int n, int[] array)
{
if (g == 1)
return true;
else
if (j == n)
return false;
else
return checkGCD(GcdTester.gcd(g, array[j]), j + 1, n, array);
}``````

#### Sunius

##### Distinguished
n should be size of the array. And yes, it's still considered recursive. It works for me. The code for the whole program:

Code:
``````using System;

namespace test1
{
class Program
{
static void Main(string[] args)
{
int[] A = {6, 20, 90, 40, 42, 50, 90, 4, 2};
int[] B = {7, 8, 9, 50, 11, 44, 7, 8, 9, 7};

checkGCD(A);
checkGCD(B);
}

public static int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}

public static bool checkGCD(int g, int j, int n, int[] array)
{
if (g == 1)
return true;
else if (j == n)
return false;
else
return checkGCD(gcd(g, array[j]), j + 1, n, array);
}

public static void checkGCD(int[] array)
{
if (checkGCD(array, 1, array.Length, array))
Console.WriteLine("All the numbers in the array are coprime.");
else
Console.WriteLine("Numbers in the array are not coprime.");
}
}
}``````
Output:
Code:
``````Numbers in the array are not coprime.
All the numbers in the array are coprime.``````

#### ZKR

##### Honorable
Wow Const, it`s ingenious, I am quite ashame of my cumbersome gcd
Code:
``````public static int gcd (int n, int m)
{
int larger, smaller, commonGD;
if (n > m)			 // Determines greater integer then assigns values for further processing
{
larger = n;
smaller = m;
}
else
{
larger = m;
smaller = n;
}

int dividable, temp;		// Processes forward to get gcd
do
{
commonGD = smaller;
dividable = larger / smaller;
larger -= smaller * dividable;
temp = larger;
larger = smaller;
smaller = temp;
}
while (larger != 1 && smaller != 0);
System.out.println (str + commonGD);
return (commonGD);
}``````
I don`t know why but your code didn`t find the correct "coprimeness". I changed it to :
Code:
``````public static boolean checkGCD(int[] array)
{
if (checkGCD(array, 1, array.length, array))
return true;
else
return false;``````
and:
Code:
``````if (TEMP.checkGCD (list))
System.out.println("All the numbers in the array are coprime." );
else
System.out.println("Numbers in the array are not coprime." );``````
And the results are:
"
4, 7, 8, 9,
All the numbers in the array are coprime.
"
but 4 and 8 have a gcd of 4.

NOW, I have meanwhile wrote my (crude?) code:
Code:
``````public static boolean checkGCD (int[] values)
{
boolean result;
int num1 = 0, num2 = num1+1;

if (GcdTester.checkGCD(num1, num2, values))
result = true;
else
return false;
return result;
}

public static boolean checkGCD (int num1, int num2, int[] values)
{
boolean result;

if (GcdTester.gcd (values[num1], values[num2]) == 1)
result = true;
else
return false;

if (num2 < values.length-1 && num1 != num2)
GcdTester.checkGCD(num1, num2+1, values);

if (num1 < values.length-2 && num2 < values.length-1 && num1 != num2)
GcdTester.checkGCD(num1+1, num2, values);
return result;
}``````
Now it goes well until the pre-last number (num1) but then checks it with itself. f.e: 1,2,3 : checks 1,2 1,3 2,2
second problem is that it doesn`t always return the right result (I leave that for the second stage).
Is my code too crude, can you point on it`s mistakes, or retest your code.

Thanks for the great help by now.

#### Sunius

##### Distinguished
So wait. Wasn't your task to tell whether the largest common divider for all the numbers is 1 or is another number? If not, what is your task?

I'm asking this because array of {4, 7, 8, 9} GCD is 1. So the program is outputting true correctly. I must have misunderstood your task?

#### ZKR

##### Honorable

gcd method:
To find the gdc of 2 integers (accepting (int num1, int num2)

checkGCD method:
to assure that all numbers in the array are gdc=1 with each other. It checks all numbers in the array with all others.

So that : {4, 7, 8, 9}
is checked:
4, 7 | 4,8 | 4,9
7,8 | 7,9 |
8,9

Although in would stop when 4,8 is reached because it`s gdc is 4. But the issue is to check all with all, until a higher that 1 gcd is found (then false) or

#### Sunius

##### Distinguished
Okay I fixed it. It works just like you said it needed to. However, that is one strange task.

Code:
``````using System;

namespace test1
{
class Program
{
static void Main(string[] args)
{
int[] A = {6, 20, 90, 40, 42, 50, 90, 4, 2};
int[] B = {7, 8, 9, 50, 11, 44, 7, 8, 9, 7};

checkGCD(A);
checkGCD(B);
}

public static int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}

public static bool checkGCD(int i, int j, int n, int[] array)
{
if (gcd(array[i], array[j]) != 1)
return false;
else if (j < n - 1)
return checkGCD(i, j + 1, n, array);
else if (i < n - 2)
return checkGCD(i + 1, i + 2, n, array);
else
return true;
}

public static void checkGCD(int[] array)
{
if (checkGCD(array, 1, array.Length, array))
Console.WriteLine("All the numbers in the array are coprime.");
else
Console.WriteLine("Numbers in the array are not coprime.");
}
}
}``````

#### ZKR

##### Honorable
When tested for :
1, 3, 5, 7, 11,

(I have inserted a println in gcd)

result:
CGD of 3 and 3 is : 3
Numbers in the array are not coprime.

It only checked those values, and checked one with itself.

#### Sunius

##### Distinguished
Yea my bad The actual call of checkGCD should be:

Code:
``checkGCD(0, 1, array.Length, array)``
Code:
``checkGCD(array, 1, array.Length, array))``

#### ZKR

##### Honorable
Well, meanwhile I have completed my own version.
It might be a mammoth, but it was obtained by sweat and blood.
Some of the fixes were done thanks to your help, thanks.

my code:
Code:
``````public static boolean checkGCD (int[] values)
{
int num1 = 0, num2 = num1+1;
return (GCD.checkGCD(num1, num2, values));
}

public static boolean checkGCD (int num1, int num2, int[] values)
{
boolean result = false;
int gcd = GCD.gcd(values[num1], values[num2]);
if (gcd == 1)
{
if (num1 == values.length-2 && num2 == values.length -1)
result = true;
else
{
if (num1 < values.length-2 && num2 <= values.length -1)
{
int next1 = GCD.next1 (num1, num2, values);
int next2 = GCD.next2 (num1, num2, values);
if (next1 == num1+1)
next2 = next1+1;
System.out.println ("next1: " + next1 + " next2: " + next2);
result = GCD.checkGCD(next1, next2, values);
}
}
}
return result;
}

public static int next1 (int num1, int num2, int[] values)
{
//if (num2 < values.length && num1 < values.length - 2);
if (num2 == values.length - 1 && num1 < values.length -1)
num1 += 1;
return num1;
}

public static int next2 (int num1, int num2, int[] values)
{
if (num2 < values.length - 1)
num2 += 1;
return num2;
}``````

I`ll try to analyze your code tomorrow to understand how it works, and where I did wrong (too complicated).

Great Thanks for the help.

#### Sunius

##### Distinguished
Glad I helped .