# C Program to Find GCD Using Recursion

In this tutorial, we’ll create a C program to find the Greatest Common Divisor (GCD) of two numbers using recursion. GCD is the largest positive integer that divides each of the numbers without leaving a remainder. We’ll employ a recursive algorithm to calculate the GCD efficiently. Let’s dive into the details of the algorithm and the C code.

## GCD Calculation Algorithm

1. Base Case: If is 0, return (base case for GCD).
2. Recursive Call: If is not 0, recursively call the GCD function with and .

## C Program for Finding GCD Using Recursion

#include <stdio.h>

// Function to find GCD using recursion
int gcd(int a, int b) {
// Base case
if (b == 0) {
return a;
} else {
// Recursive call
return gcd(b, a % b);
}
}

int main() {
int num1, num2;

// Input from user
printf("Enter two positive integers: ");
scanf("%d %d", &num1, &num2);

// Check if the inputs are positive
if (num1 <= 0 || num2 <= 0) {
} else {
// Compute and display GCD
printf("GCD of %d and %d = %d\n", num1, num2, gcd(num1, num2));
}

return 0;
}


## Output Example

### Example 1: Positive Integers

Enter two positive integers: 48 18
GCD of 48 and 18 = 6


### Example 2: Zero

Enter two positive integers: 35 0
GCD of 35 and 0 = 35


### Example 3: Negative Integers

Enter two positive integers: -15 20


## Explanation

1. GCD Function: The gcd function is defined to calculate the GCD of two positive integers using recursion.
2. Base Case: The base case checks if the second number () is 0, in which case the GCD is the first number ().
3. Recursive Call: If is not 0, the function recursively calls itself with and .

## Conclusion

This C program efficiently computes the GCD of two positive integers using a recursive approach. The recursive nature of the algorithm allows for an elegant solution to the GCD calculation.

Feel free to experiment with different pairs of positive integers and observe how the GCD is computed. Understanding recursion is essential for implementing various algorithms efficiently.

If you have any questions or need further clarification, please don’t hesitate to ask!