GCD using Recursion in C Program

In this blog post, we will checkout the GCD using recursion in C programming. Finding the greatest common divisor (GCD) or highest common factor (HCF) of two numbers is a fundamental concept in mathematics with many practical applications. The GCD represents the largest number that divides two given numbers without leaving a remainder.

For example, let’s find the GCD of 12 and 18:

First, we factor the numbers:

12 = 2 x 2 x 3

18 = 2 x 3 x 3

We look for the largest factor common to both numbers. In this case, it is 2 x 3 = 6.

So the GCD of 12 and 18 is 6.

Now that we understood what GCD is, let’s see how to find gcd of two numbers using recursion in C.

To write a C program for finding the gcd of two numbers, you can follow this algorithm and corresponding pseudo code.

Algorithm:

1. Take two integers as input – a and b
2. If b == 0, return a (base case)
3. Else, call the function again with b and a%b as arguments

GCD using Recursion in C Program

#include <stdio.h>

int GCD(int a, int b){
  if(b == 0)
    return a;
  else
    return GCD(b, a%b);
}

int main() {
  int a, b;
  printf("Enter two positive integers: ");
  scanf("%d %d", &a, &b);
  printf("GCD(%d, %d) = %d\n", a, b, GCD(a,b));
  return 0;
}

Output

In the above program,

• The GCD function takes two integers a and b
• It checks if b is 0, if yes returns a (base case)
• Otherwise, it calls GCD again recursively with b and a%b as arguments
• This repeats until b becomes 0, then the stack unwinds and we get the GCD

The execution flow for the input values 16 and 24 would unfold as follows:

• Initial Call: GCD(16, 24)
  • Calls GCD(24, 16 % 24) => GCD(24, 16)
    • Calls GCD(16, 24 % 16) => GCD(16, 8)
      • Calls GCD(8, 16 % 8) => GCD(8, 0)
        • Since the second parameter is now 0, the base case is met, and the function returns 8.

Thus, the output of the program would be “GCD(16, 24) = 8”, indicating that the greatest common divisor of 16 and 24 is 8.

Conclusion

In this blog post we first discussed what gcd is and then we delved into how to find gcd of two numbers in c using recursion.

If you liked this post you can checkout other C Programs.