Running Time of GCD Function Recursively (Euclid Algorithm)

Question

I have only been able to find posts about how to implement the gcd function both recursively and iteratively, however I could not find this one. I am sure it's on Stackoverflow however I could not find it so I apologize if it's a duplicate post.

---

I have looked at the analysis on Wikipedia (here) and could not understand their recurrence relation.

Consider the following implementation of the GCD function recursively implemented in C. It has a pre condition that both numbers must be positive, however irrelevant for the run time.

int gcd( int const a, int const b ) {
  // Checks pre conditions.
  assert( a >= 0 );
  assert( b >= 0 );

  if ( a < b ) return gcd( b, a );

  if ( b == 0 ) return a;

  return gcd( b, a % b );
}

Performing an analysis on the run time I find that every operation is O(1) and hence we know the recurrence relation thus far is: T(n) = O(1) + ???. Now to analyze the recursive call, I am not sure how to interpret a (mod b) as my recursive call to properly state my recurrence relation.

Answer 1

At each recursive step, gcd will cut one of the arguments in half (at most). To see this, look at these two cases:

If b >= a/2 then on the next step you'll have a' = b and b' < a/2 since the % operation will remove b or more from a.

If b < a/2 then on the next step you'll have a' = b and b' < a/2 since the % operation can return at most b - 1.

So on each recursive step, gcd will cut one of the arguments in half (at most). This is O(log(N)) steps where N is the max of the initial a and b.