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

23 comments:

  1. 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();
    }

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

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

      Delete
  2. prashant is wrong his program is incorrect...........

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

    ReplyDelete
  4. programm can not run correctly
    mahadevan

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

    ReplyDelete
  6. prrashant do itusing recursion

    ReplyDelete
  7. 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

    ReplyDelete
  8. Brilliant program Prashanth!

    ReplyDelete
  9. 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);
    }

    ReplyDelete
  10. yenna da epadi savu adiguringa

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

    ReplyDelete
  12. plz explain working

    ReplyDelete
  13. frnds pls give a crct program fr gcd by using recursion

    ReplyDelete
    Replies
    1. #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);
      }

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

      Delete
  14. This comment has been removed by the author.

    ReplyDelete
  15. #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;
    }
    }
    }

    ReplyDelete
  16. 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);
    }

    ReplyDelete
  17. 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.

    ReplyDelete
  18. 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

    ReplyDelete