C program to find GCD of two numbers using recursion

       Whenever solution to the problem is approached with recursive fashion, the solution to that problem is decomposed into a certain number of small tasks (i.e., recursive calls) which together gives the complete solution. These recursive calls stop at one particular condition that condition is called as base condition. So every recursive function needs two criteria. One is base criteria and another one is recursive criteria. In this program, the recursive criteria is ‘return gcd(b, remainder)’ which computes the gcd of ‘b’ and ‘remainder’ and the base criteria is ‘if(remainder==0) return b’ which supplies the variable ‘b’to the recursive call. In this way, GCD of two numbers is computed using the recursive function. In this program we find GCD using recursion.

GCD using recursion program in c language



Source Code for finding GCD using recursion :

#include<stdio.h>
int gcd(int, int); 
int main()
{
	int i,j;
	printf("\n Enter the numbers :");
	scanf("%d %d",&i,&j);                      //Step 1
	printf("\n The GCD of %d and %d is %d",i,j,gcd(i,j)); //Step 2 
	return 0;
}

int gcd(int a,int b)
{
	int remainder;
	remainder = a % b;
	if(remainder == 0)        //Step 3
	   return b;
	else
	  return gcd(b, remainder); //Step 4
}


edit-code-image

Sample Test cases:

1.   Enter the numbers :5 1
     The GCD of 5 and 1 is 1

2.   Enter the numbers :5 25
     The GCD of 5 and 25 is 5

Explanation:

Step 1: The numbers are read from the user using scanf() function.

Step 2: The recursive function gcd(i,j) is called from the main program which prints the value evaluted from the recursive call.

Step 3: This base condition returns the value of ‘b’ which is a staring point of execution for the recursive call.

Step 4: The recursive function ‘gcd(b,remainder)’ helps to evaluate the value after evaluation of base condition.

More Insights:

1. More about execution of recursive function.

1. Explanation of recursive function execution (video).

More Content:C Programming
Explore C Programs:C Programs