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); }