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

## More from: Mathematics

- Recursively Finding Greatest Common Divisor (GCD) – Java Implementation
- In Place Matrix (2D Array) Clockwise and Counterclockwise Rotation – Java Implementation
- Matrix (2D Array) Clockwise and Counterclockwise Rotation with Extra Buffer – Java Implementation
- Prime Number Finder In Java
- Printing Fibonacci Sequence Using Recursive and Iterative Methods
- Finding Square Root Of A Double Number In Java Using Binary Search
- How to swap two variables without using extra temporary variable?
- Rotating a two dimensional integer array In-Place and using extra memory
- Finding Mean Value Of An Integer Array In Java

we need the the square root of the number, not the number itself.

squareRoot = midValue * midValue;

if (squareRoot == number) {

return squareRoot;

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

Thank you Sabrina for the feedback.