🔖
【ユークリッドの互除法】再帰関数を用いた最大公約数の求め方
function gcd(m, n) {
if ((m % n) == 0){
// ベースケース
return n;
} else {
return gcd(n, m % n);
}
}
m < nの場合(割られる方が割る方より値が小さい場合)どうなるの?と一瞬思いましたが、その場合答えは0で割られる方がそのまま余りとなるので問題ないです。
例
gcd(44,242);
↓
m=44, n=242の場合、処理の中でgcd(242, 44%242)が実行される
↓
44%242だと割られる方が割る方より値が小さいので、割られる方がそのまま余りとなります。
つまり以下となりmとnが入れ替わった形になります。
gcd(44,242)
↓ gcd(242, 44%242)
gcd(242, 44)
おまけ
3つの自然数 x, y, z が与えられるので、x, y, z の最大公約数を返す
// gcd関数のaをgcd(x,y)に、bをzにそれぞれ置換するだけ。逆でもOK
function threeGCD(x, y, z) {
if (gcd(x,y) % z == 0) return z;
return gcd(z, gcd(x,y)%z);
}
// function threeGCD(x, y, z) {
// if (z % gcd(x,y) == 0) return gcd(x,y);
// return gcd(gcd(x,y), z%gcd(x,y));
// }
function gcd(a, b) {
if (a % b == 0) return b;
return gcd(b, a%b);
}
参考
Discussion