続･ユークリッドの互除法を使って2つの整数の最大公約数を求める（再帰編）

今度は、再帰を使って書いてみました。
まずは、減算を用いたユークリッド互除法です。

public class Euclid {
	private static int count;
	public static void main(String[] args){
		try{
			int m = Integer.parseInt(args[0]);
			int n = Integer.parseInt(args[1]);

			System.out.println("最大公約数：" + gcd(m, n) + ", 計算回数：" + count);			
		}catch(Exception e){
			e.printStackTrace();
		}
	}
	private static int gcd(int m, int n){
		if(m == n) return m;
		if(m > n){
			m = gcd(m - n, n);
		}else{
			m = gcd(m, n - m);
		}
		count++;
		return m;
	}
}

次に、剰余を使ったユークリッド互除法。

public class Euclid {
	private static int count;
	public static void main(String[] args){
		try{
			int m = Integer.parseInt(args[0]);
			int n = Integer.parseInt(args[1]);

			System.out.println("最大公約数：" + gcd(m, n) + ", 計算回数：" + count);			
		}catch(Exception e){
			e.printStackTrace();
		}
	}
	private static int gcd(int m, int n){
		if(n == 0){
			return m;
		}else{
			m = gcd(n, m % n);
		}
		count++;
		return m;
	}
}

再帰版と非再帰版のコードを見比べてみると、再帰版のコードの方が簡潔に書けていると思います。

前回と同じ引数（1071、81）を渡して実行すると、結果は次のようになります。
ここで、計算回数に注目すると再帰版と非再帰版で計算回数は同じ結果が得られることが分かります。
フィボナッチ数列のときは、再帰を使うと計算効率は落ちましたがユークリッド互除法は落ちていません。
従って、必ずしも再帰を使ったプログラムは計算効率が悪いとは言えないのです。
再帰を使う場合は、計算効率を考慮し、それが有効なのかをしっかり検討する必要がありますね。。

減算の場合

最大公約数：9, 計算回数：18

剰余の場合

最大公約数：9, 計算回数：3