Algorithm

  1. Include Header File:

    c
    #include <stdio.h>

  2. Function Prototype: Declare the function GCD with two integer parameters (x and y).

    c
    int GCD(int x, int y);

  3. Main Function:

    c
    int main(){ int a, b; // Asking for Input printf("Enter Two Positive Integers: \n"); scanf("%d\n %d", &a, &b); printf("GCD of %d and %d is %d.", a, b, GCD(a, b)); return 0; }

    This function does the following:

    • Declares two integer variables a and b.
    • Asks the user to input two positive integers.
    • Reads the input using scanf.
    • Calls the GCD function with the input values and prints the result.

  4. GCD Function:

    c
    int GCD(int x, int y){ if( y != 0) return GCD(y, x % y); else return x; }

    This function calculates the GCD using the Euclidean algorithm, which states that the GCD of two numbers x and y is the same as the GCD of y and x % y. The recursion continues until y becomes 0. When y becomes 0, the function returns the value of x as the GCD.

    • If y is not 0, it calls itself recursively with arguments y and x % y.
    • If y is 0, it returns the value of x as the GCD.

The program takes two positive integers as input, calls the GCD function with these inputs, and then prints the GCD of the two numbers. The GCD function uses recursion to apply the Euclidean algorithm until a base case is reached.

 

Code Examples

#1 Code Example- C Program to Find GCD of Two Numbers Using Recursion

Code - C Programming

// C Program To Find GCD of Two Number Using Recursion
#include <stdio.h>
int GCD(int x, int y);
int main(){
    int a, b;
    
    // Asking for Input
    printf("Enter Two Positive Integers: \n");
    scanf("%d\n %d", &a, &b);
    
    printf("GCD of %d and %d is %d.", a, b, GCD(a, b));
    return 0;
}

int GCD(int x, int y){
    if( y != 0)
        return GCD(y, x % y);
    else 
        return x;
}
Copy The Code & Try With Live Editor

Output

x
–
+
cmd
Enter Two Positive Integers:
40
412
GCD of 40 and 412 is 4.
Advertisements

Demonstration

C Programing Example to Find GCD of Two Numbers Using Recursion-DevsEnv

Next
Appending into a File in C Programming