# Greatest Common Divisor - GCD

Recursion Algorithm

Share

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