C Exercises: Find GCD of two numbers

Last update on March 20 2025 12:37:53 (UTC/GMT +8 hours)

7. GCD Recursion Variants

Write a program in C to find the GCD of two numbers using recursion.

Pictorial Presentation:

Sample Solution:

C Code:

#include<stdio.h>

int findGCD(int num1,int num2);
int main()
{
  int num1,num2,gcd;
  printf("\n\n Recursion : Find GCD of two numbers :\n");
  printf("------------------------------------------\n");  
  printf(" Input 1st number: ");
  scanf("%d",&num1);
  printf(" Input 2nd number: ");
  scanf("%d",&num2);
  
  gcd = findGCD(num1,num2);
  printf("\n The GCD of %d and %d is: %d\n\n",num1,num2,gcd);
  return 0;
}

int findGCD(int a,int b)
{
     while(a!=b)
     {
          if(a>b)
              return findGCD(a-b,b);
          else
             return findGCD(a,b-a);
     }
     return a;
}

Sample Output:

 Recursion : Find GCD of two numbers :                                                                        
------------------------------------------                                                                    
 Input 1st number: 10                                                                                         
 Input 2nd number: 50                                                                                         
                                                                                                              
 The GCD of 10 and 50 is: 10

Explanation:

int findGCD(int a,int b)
{
     while(a!=b)
     {
          if(a>b)
              return findGCD(a-b,b);
          else
             return findGCD(a,b-a);
     }
     return a;
}

This function findGCD() takes two integers as parameters (int a, int b) and repeatedly subtracts the smaller number from the larger number until they become equal. When they become equal, the function returns the value of either one of them as the GCD.

Flowchart:

For more Practice: Solve these Related Problems:

Write a C program to compute the LCM of two numbers using a recursive GCD function.
Write a C program to find the GCD of three numbers recursively.
Write a C program to implement the subtraction-based method for GCD recursively.
Write a C program to display the recursion depth while computing the GCD of two numbers.

C Programming Code Editor:

Previous: Write a program in C to find the sum of digits of a number using recursion.
Next: Write a program in C to get the largest element of an array using recursion.