Table of Contents

ToggleIn 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:**

- Take two integers as input – a and b
- If b == 0, return a (base case)
- 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.

- Calls

- Calls

- Calls

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.