Effective way of finding GCD of 2 numbers using recursive approach-CodePudding

I have been recently solving a problem to find GCD/HCF of two numbers using Recursion. The first solution that came to my mind was something like given below.

long long gcd(long long a, long long  b){
   if(a == b) return a;
   return gcd(max(a, b) - min(a, b), min(a, b));
}

I saw other people's solutions and one approach was very common which was something like given below.

long long gcd(long long a, long long b){ 
  if(!b) return a;
  return gcd(b, a % b);
}

What is the difference between the Time Complexities of these two programs? How can I optimise the former solution and how can we say that the latter solution is efficient than any other algorithm?

CodePudding user response：

What is the difference between the Time Complexities of these two programs?

If you are talking about the time complexity, then you should consider the big-O notation. The first algorithm is O(n) and the second one isO(logn), where n = max(a, b).

How can I optimise the former solution?

In fact, the second algorithm is a straigtforord optimization of the first one. In the first solution, if the gap between a and b is huge, it takes many subtractions for a - b to reach the remainder a % b. So we can improve this part by using the integer modulo operation instead, which yields the second algorithm.