title: Running Time of GCD Function Recursively (Euclid Algorithm)
body: <p>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.</p>
  
  <hr>
  
  <p>I have looked at the analysis on Wikipedia (<a href="http://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency" rel="nofollow">here</a>) and could not understand their recurrence relation.</p>
  
  <p>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.</p>
  
  <pre><code>int gcd( int const a, int const b ) {
    // Checks pre conditions.
    assert( a &gt;= 0 );
    assert( b &gt;= 0 );
  
    if ( a &lt; b ) return gcd( b, a );
  
    if ( b == 0 ) return a;
  
    return gcd( b, a % b );
  }
  </code></pre>
  
  <p>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.</p>