Mumbai University > Computer Engineering > Sem 3 > Data structures

Marks: 5 M

Year: May 14

• Here is the recursive function to calculate the GCD of two numbers a and b:-

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

• Here is the non-recursive version:-

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