FIND GCD OF A NUMBER USING RECURSION IN C PROGRAM





Find gcd of a number using recursion in c program


#include<stdio.h>
int main(){
  int n1,n2,gcd;
  printf("\nEnter two numbers: ");
  scanf("%d %d",&n1,&n2);
  gcd=findgcd(n1,n2);
  printf("\nGCD of %d and %d is: %d",n1,n2,gcd);
  return 0;
}

int findgcd(int x,int y){
     while(x!=y){
          if(x>y)
              return findgcd(x-y,y);
          else
             return findgcd(x,y-x);
     }
     return x;
}





Sum of n numbers using recursion in c
Matrix multiplication using recursion in c
Multiplication using recursion in c
Lcm using recursion in c
Using recursion in c find the largest element in an array
Prime number program in c using recursion
Decimal to binary conversion in c using recursion
C program for fibonacci series using recursion
Reverse a string using recursion
Write a program for palindrome using recursion
Find factorial of a number using recursion in c program
Find gcd of a number using recursion in c program
Find sum of digits of a number using recursion using cprogram
Find power of a number using recursion using c program
Binary search through recurssion using c program
Reverse a number using recursion in c program
Big list of c program examples

32 comments:

Prashanth said...

s it can b made simpler...

int gcd(int m ,int n)
{
if(m==0)
return(n);
if(n==0)
return(m);
return(n,m%n);
}
void main()
{
int m,n;
clrscr();
printf("enter 2 numbers");
scanf("%d%d",&m,&n);
printf("gcd is %d",gcd(m,n));
getch();
}

abhinav said...

prashant is wrong his program is incorrect...........

Anonymous said...

He is correct but he wrote return(n,m%n); instead of gcd(n,m%n); in 7th line of his program

alexandrodlavega said...

I try it now..

Anonymous said...

programm can not run correctly
mahadevan

Anonymous said...

Prashanth your program is correct but it would be better if u had done the program with recursion

Anonymous said...

prrashant do itusing recursion

Capt Jack Sparrow said...

using recursion is not advisable in this prog because depth of recursion will be huge if no supplied by users are big..in that case time complexity of prog will tend to its worst case ..i agree strongly with abhinav's way of coding

Anonymous said...

Brilliant program Prashanth!

Anonymous said...

int gcd(int n, int m)
{
int gcdVal = 0;
if(m>n)
{
gcdVal = gcdRec(m,n,n);
}
else
{
gcdVal = gcdRec(n,m,m);
}



}

int gcdRec(int m, int n, int k)
{
if(m%k==0 && n%k==0)
return k;

gcdRec(m,n,k-1);
}

Anonymous said...

yenna da epadi savu adiguringa

Anonymous said...

Prashant is correct......instead of writing return gcd(n,m%n) he wrote return (n,m%n)

Anonymous said...

IT'S VERY HEPLFULL TO ME.
NICE GOOD JOB...........

Anonymous said...

plz explain working

Vijai Vicky said...

frnds pls give a crct program fr gcd by using recursion

Anonymous said...

#include
#include
void main()
{
int gcd(int,int);
int a,b;
printf("enter the two numbers");
scanf("%d%d",&a,&b);
printf("gcd is %d",gcd(a,b));
getch();
}
int gcd(int a,int b)
{
if(a%b==0)
{
return b;
}
else
return gcd(b,a%b);
}

aman kesharwani said...
This comment has been removed by the author.
aman kesharwani said...

#include
int main()
{
int n1,n2,i,min;
printf("enter 2 numbers");
scanf("%d %d", &n1,&n2);

min = n1 < n2 ? n1: n2;
for ( i= min; i>=1; i-- )
{
if(n1%i==0 && n2%i==0)
{
printf("hcf is %d ",i);
break;
}
}
}

shilpa.T said...

it can also be written as

#include
void main()
{
int gcd(int,int);
int a,b;
printf("enter a,b values \n");
scanf("%d%d",&a,&b);
printf("gcd of %d,%d is %d",a,b,gcd(a,b));
getch();
}
int gcd(int a,int b)
{
if(a>b)
gcd(b,a);
if(a==0)
return(b);
else
gcd(b%a,a);
}

Anonymous said...

hahahah... try it dude! if u enter 24 & 12 its returning 0... it is not correct

Anonymous said...

This is a decent program, but it does not work for all cases. Try passing in findgcd(10, 0). It fails!!! Because the functions goes into an infinite recursion that never ends.

Anonymous said...

i think the input of a has to be greater than b in this case. isn't it ?

Anonymous said...

Guys it would be better if you check for any idiot entering 0 as one of the two numbers, in that case it may print the non zero number as the gcd for some programs or, it could cause an infinite repetition of the loop for some other programs .... its better if you print it as an error as soon as 0 is entered

Ajay Menon said...
This comment has been removed by the author.
Sai Reddy said...

it was not getting it is showing gcd of 12 and 8 is 8

Sai Reddy said...

it was not getting it is showing gcd of 12 and 8 is 8

vikram mahale said...

int gcd(int x, int y)
{ return (y==0) ? x : gcd(y, x%y); }

rahul meena said...
This comment has been removed by the author.
rahul meena said...

int findGcd(int a, int b)
{
Static int i=1,gcd=1;
if(i>b)
{
return gcd;
}
if(b%i==0&&a%i==0)
{
gcd=i;
}
findGcd(a,b);
}

madhu chinna said...

Try this very simple process in bits vizag
#include
Int gcd(int,int);
main()
{
Int a,b,r;
clrscr();
Print("enter the values of a,b");
Scanf("%d%d",&a,&b);
R=Gcd(a,b);
Print("the gcd value is=%d,r);
}
Int gcd(int x,int y)
{
If(y==0)
return x;
else
gcd(y,y%x);
}

vilas kaware said...

Guys, can u please tell me which is the correct prog??

Fayaz Sayed said...

Which is wrt yar