c - GCD 関数の再帰的な実行時間 (Euclid アルゴリズム)

Question

gcd 関数を再帰的および反復的に実装する方法に関する投稿しか見つけることができませんでしたが、これは見つかりませんでした。Stackoverflowにあると思いますが、見つけられなかったので、重複した投稿である場合はお詫び申し上げます。

---

ウィキペディアの分析 (こちら) を見ましたが、それらの再帰関係を理解できませんでした。

C で再帰的に実装された GCD 関数の次の実装を検討してください。これには、両方の数値が正でなければならないという前提条件がありますが、実行時間には関係ありません。

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 );
}

ランタイムの分析を実行すると、すべての操作が O(1) であることがわかります。したがって、これまでの再帰関係は T(n) = O(1) + ??? であることがわかります。再帰呼び出しを分析するために、 a (mod b) を再帰呼び出しとして解釈して、再帰関係を適切に記述する方法がわかりません。