RECURSIVE COMPUTATION OF GCD (m,n) where $$ m\gt n$$

The greatest common divisor (gcd) of two numbers is the largest integer that divides both numbers. For example the gcd (22,11) is 11 while the gcd(36,18) is 18. We will use Euclid's method to calculate the gcd.

Definition of gcd(m,n) where m > n

    gcd(m,n) = n if n is a divisor of m
    gcd(m,n) = gcd(n,m % n) if n is not a divisor of m where m % n is the integer reminder of m divided by n

Using above formula, GCD(21,15) = GCD(15,21 % 15) = GCD (15,6) = GCD(6,15 % 6) = GCD (6,3) = 3 because 3 is a divisor of 6.

Recursive Algorithm is given below:

RecursiveGCD(m,n)
1 if n is a divisor of m result = n
2 else
3 result = RecursiveGCD(n, m % n)

JAVA IMPLEMENTATION

import java.util.Scanner;

/**
 * Created by Ganesh.r.hegde on 16-Feb-18.
 */
public class GCD {

    public static void main(String[] args) {

        System.out.println("Enter first positive number :");
        Scanner scanner = new Scanner(System.in);

        int n1 = scanner.nextInt();

        if(n1<=0)
            throw new IllegalArgumentException("Positive integer expected");
        else
            System.out.println("Enter second positive number :");

        int n2 = scanner.nextInt();

        if(n2<=0)
            throw new IllegalArgumentException("Positive integer expected");
        else
        {
            System.out.println("The GCD of "+n1+ " and "+n2+" is "+calcGCD(n1,n2));
        }

    }

    /** Recursive gcd method.
     pre: m > 0 and n > 0
     @param m The larger number
     @param n The smaller number
     @return Greatest common divisor of m and n
     */
    public static double calcGCD(int m, int n) {

        if (m % n == 0)
            return n;
        else
            return calcGCD(n, m % n);
    }

}

VERIFICATION OF CORRECTNESS

The base case is "n is a divisor of m".If so, the solution is n (n is the gcd) which is correct. We need to check whether the recursive case makes progress to the base case. In each successive recursive call, the arguments are smaller than the previous call and the new second argument is always smaller than the new first argument ( m % n < n). Eventually a divisor will be found or the second argument will become 1.Since 1 divides every integer, n = 1 becomes the base case. This proves that the recursive case makes progress towards the base case.

If m < n in the initial call to the recursive method then m % n = m and the arguments get swapped in the second recursive call.

TAIL RECURSION

gcd method discussed above is a method of tail recursion. In tail recursion, the last thing a method does is to call itself. Both tail recursion and iteration enable us to repeat a compound statement. In iteration, a loop repetition condition in the loop header determines whether we repeat the loop body or exit from the loop. We repeat the loop body while the repetition condition is true. In tail recursion, the condition usually tests for a base case. In a recursive method, we stop the recursion when the base case is reached (the condition is true), and we execute the method body again when the condition is false.We can always write an iterative solution to any problem that is solvable by recursion.