Recursion Algorithm
In this tutorial we will learn to find GCD or Greatest Common Divisor using recursion.
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.
GCD(x, y) Begin if y = 0 then return x; else Call: GCD(y, x%y); endif End
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
#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); }