Recursively Finding Greatest Common Divisor (GCD) – Java Implementation

This articles shows a java program that finds a greatest common divisor between two input integers and also prints the intermediate steps of recursion. Can you think about the complexity of this algorithm? It is O(Log(N)) where N is the largest number of the two. See the analysis here.

package com.icodejava.research.ready;
/**
 * 
 * @author Kushal Paudyal
 * Created on: 2/8/2017
 * Last Modified on: 2/8/2017
 * 
 * Recursive way of finding the GCD (Greatest Common Divisor)
 */
public class GCDRecursive {
	
	 public static int gcd(int a, int b) {
		 System.out.println("First Number: " + a + " Second Number: " + b);
	        if (a < 0 || b < 0) {
	            throw new IllegalArgumentException("No GCD of negative integers");
	        }
	        return b == 0 ? a : gcd(b, a % b);
	    }
	 
	 public static void main(String args []) {
		 System.out.println("Greatest Common Divisor of 35 and 21 is " + gcd(35,21));
	 }

}

The following is the output of this program.

First Number: 35 Second Number: 21
First Number: 21 Second Number: 14
First Number: 14 Second Number: 7
First Number: 7 Second Number: 0
Greatest Common Divisor of 35 and 21 is 7

Tagged , , , , , , . Bookmark the permalink.

3 Responses to Finding Mean Value Of An Integer Array In Java

  1. Jerry says:

    we need the the square root of the number, not the number itself.
    squareRoot = midValue * midValue;

    if (squareRoot == number) {
    return squareRoot;

  2. Sabrina Kundu says:

    Hi Kushal,

    This program works for some cases, but not all. For example, 4 prints out 4.0 when it is supposed to print out 2.0. Fortunately, I found the mistake. If you change “if (squareRoot == number) return squareRoot;” to “if(squareRoot == number) return midValue;”, then the program prints out the correct square root for even numbers.

    Thanks,

    Sabrina

Leave a Reply

Your email address will not be published. Required fields are marked *