Solved

# Recursive boolean

Tags:
Last response: in Applications
Share
June 26, 2012 6:36:26 PM

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?

`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?

a b L Programming
June 26, 2012 10:20:06 PM

ZKR said:
Does it involves using a linked list somehow?

No, I don't think so, but you need to loop through the array. . .
m
0
l
a b L Programming
June 26, 2012 11:49:08 PM

Something like this:
`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
`GcdTester(array[0], 1, n, array);`

m
0
l
Related resources
June 27, 2012 12:37:10 PM

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:
`public static boolean checkGCD (int[] values)	{			int n = values.length;		if (GcdTester.checkGCD(values[0], 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);}`
m
0
l
a b L Programming
June 27, 2012 1:56:32 PM

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

`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);            Console.ReadLine();        }         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[0], 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:
`Numbers in the array are not coprime.All the numbers in the array are coprime.`
m
0
l
June 27, 2012 3:17:19 PM

Wow Const, it`s ingenious, I am quite ashame of my cumbersome gcd
`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 :
`public static boolean checkGCD(int[] array)        {            if (checkGCD(array[0], 1, array.length, array))					return true;            else					return false;`

and:
`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:
`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.
m
0
l
a b L Programming
June 27, 2012 9:08:46 PM

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?
m
0
l
June 28, 2012 7:40:24 AM

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

m
0
l
a b L Programming
June 28, 2012 8:55:50 AM

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

```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[0], 1, array.Length, array))
Console.WriteLine("All the numbers in the array are coprime.");
else
Console.WriteLine("Numbers in the array are not coprime.");
}
}
}```
m
0
l
June 28, 2012 6:14:33 PM

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.
m
0
l

Best solution

a b L Programming
June 28, 2012 8:12:06 PM

Yea my bad   The actual call of checkGCD should be:

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

`checkGCD(array[0], 1, array.Length, array))`
Share
June 28, 2012 11:49:14 PM

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:
```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.
m
0
l
June 29, 2012 5:24:23 AM