Greatest Common Divisor - GCD

In this tutorial we will learn to find GCD or Greatest Common Divisor using recursion.

What is GCD or Greatest Common Divisor

In mathematics GCD or Greatest Common Divisor of two or more integers is the largest positive integer that divides both the number without leaving any remainder.

Example: GCD of 20 and 8 is 4.

The pseudo code of GCD [recursive]

GCD(x, y)
Begin
      if y = 0 then
          return x;
      else
          Call: GCD(y, x%y);
      endif
End

Find the GCD of 48 and 14 recursively

To find the GCD we have to divide 48 by 14.

Finding GCD:

14 ) 48 ( 3
     42
     -----
      6

Remainder is not yet zero, so we will now divide 14 by 6

14 ) 48 ( 3
     42
     -----
      6 ) 14 ( 2
          12
          -----
           2

Remainder is not yet zero, so we will now divide 6 by 2

14 ) 48 ( 3
     42
     -----
      6 ) 14 ( 2
          12
          -----
           2 ) 6 ( 3
               6
               ----
               0

Remainder is 0 so, we stop here

Therefore, the required GCD is 2

GCD code in C

#include <stdio.h>

int gcd(int x, int y);

int main(){
  int a, b, g;

  printf("Enter a and b:\n");
  scanf("%d%d", &a, &b);

  //gcd
  g = gcd(a, b);

  //in case g is negative, then convert it into positive
  if(g < 0){
    g *= -1;
  }

  //output
  printf("GCD(%d, %d) = %d\n", a, b, g);
  return 0;
}

int gcd(int x, int y){
  if(y == 0) return x;
  else gcd(y, x%y);
}