Using recursion and implementing Euclid's algorithm to find GCD of three numbers from user

Question

I am wanting to ask the user to input three numbers and then have program calculate the GCD using Euclid's algorithm all the while using recursion.

My code right now implements two input numbers. I understand the approach of calculating the GCD of a and b, and calling it result d. Then using the third input (c) and d to find the GCD and essentially repeating Euclid's algorithm again; I am not sure how to implement this in code.

import java.util.Scanner;

public class RecursionDemo {

public static void main (String[] args) {

Scanner userInput = new Scanner(System.in);

     System.out.println("Enter first number: ");
     int a = userInput.nextInt();

     System.out.println("Enter second number: ");
     int b = userInput.nextInt();


     System.out.println("GCD is: " + gCd(a, b));
   }

     public static int gCd(int a, int b) {

     if(b == 0){
         return a;
        }
     return gCd(b, a%b);         
   }
}   

The part that is really throwing me off is using recursion to solve my problem.

So far I know I need to implement:

System.out.println("Enter third number: ");
     int c = userInput.nextInt();

d = //Not sure here

//And then modify my recursion method to find GCD.

Any help or suggestions would greatly be appreciated!

Solution 1

d = gCd (a, b);
System.out.println("GCD is: " + gCd(d, c));

Note that you may call your gCd function with any two arguments, not just a and b. For better understanding and less confusion, you may want to rename its arguments, like the following:

 public static int gCd(int x, int y) {
     if(y == 0) {
         return x;
     }
     return gCd(y, x%y);
 }

So, first you call it with x = a and y = b to find GCD of a and b. Store the result into new variable d. After that, you call it again with x = d which is in turn GCD of a and b, and y = c. Thus you get the GCD of all the three numbers.

Solution 2

The gcd method can be iterated to obtain the gcd of a larger set of numbers. For example:

gCd(a, b, c) = gCd( gCd(a, b), c)

and

gCd(a, b, c, d) = gCd( gCd(a, b, c), d) so then
gCd(a, b, c, d) = gCd( gCd( gCd(a, b), c), d)

Easy, specific solution:

System.out.println("GCD is: " + gCd( gCd(a, b), c) );

---

However, if you'll notice, there is recursion going on. I've created a method that takes an array of integers as an input. It will work for an array of size three, or any size. Here are the methods:

/* returns gcd of two numbers: a and b */
public static int gCd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gCd(b, a%b);
}

/* returns gcf of an array of numbers */
public static int gCd(int[] numbers)
{
    int result = numbers[0]; // first number

    for(int i = 1; i < numbers.length; i++) {
        result = gCd(result, numbers[i]); // gcf of itself and next #
    }
    return result;
}

So, to relate it to your code:

Scanner userInput = new Scanner(System.in);

System.out.println("Enter first number: ");
int a = userInput.nextInt();

System.out.println("Enter second number: ");
int b = userInput.nextInt();

System.out.println("Enter third number: ");
int c = userInput.nextInt();

// you can do this
System.out.println("GCD is: " + gCd( gCd(a, b), c) );

// or you can do this
int[] numbers = {a, b, c};
int d = gCd(numbers);

System.out.println("GCD is: " + d);

---

Sample input/output:

Enter first number: 
12
Enter second number: 
18
Enter third number: 
30
GCD is: 6
GCD is: 6

Comments

[Admin]

Thank you, that is what I was picturing in my mind but couldn't quite get it down. Renaming my argument variables was a GREAT tip.