Solved

Recursive boolean

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?

Any help please.
13 answers Last reply Best Answer
More about recursive boolean
  1. ZKR said:
    Does it involves using a linked list somehow?

    No, I don't think so, but you need to loop through the array. . .
  2. 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);
    
  3. 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);
    }
    
  4. 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.
    
  5. 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.
  6. 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?
  7. The task are:

    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
    if it not found (all are 1) it`s true.
  8. 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);
                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 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.");
            }
        }
    }
    
  9. 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.
  10. Best answer
    Yea my bad :D The actual call of checkGCD should be:

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


    instead of
    
    checkGCD(array[0], 1, array.Length, array))
    
  11. 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.
  12. Best answer selected by ZKR.
  13. Glad I helped :).
Ask a new question

Read More

Programming Apps