Write java code to implement the euclidean algorithm for finding the greatest common factor of two positive integers. must use recursion!

/* here is code in java to find greatest common

divisor with Euclidean algorithm */

import java.util.*;

// class definition

class Main

{

   // recursive method to find gcd

public static  int Euclidean(int nm1, int nm2)

   {

   // base case

if (nm1 == 0)

 return nm2;

   // recursive call

return Euclidean(nm2 % nm1, nm1);

   }

   // driver method

public static void main (String[] args) throws java.lang.Exception

{

   try{

       // scanner object to read input

    Scanner scr=new Scanner(System.in);

    System.out.print("enter first number:");

   //  read first number

       int n1=scr.nextInt();

       System.out.print("enter second number:");

       //read second number

       int n2=scr.nextInt();

       // call the method and print the gcd

       System.out.println("greatest common factor of both number is: "+Euclidean(n1,n2));

   }catch(Exception ex){

       return;}

}

}

Explanation:

Read two number from user with scanner object and assign them to variables "n1" & "n2". Call the method Euclidean() with parameter "nm1"& "nm2".According to Euclidean algorithm, if we subtract smaller number from the larger one the gcd will not change.Keep subtracting the smaller one then we find the gcd of both the numbers.So the function Euclidean() will return the gcd of both the numbers.

Output:

enter first number:12

enter second number:39

greatest common factor of both number is: 3