アルゴリズムをコードにする練習2：最大公約数を求める

はじめに

3回目になる今回は、最大公約数を求めるやり方について見ていきます。
ここで、リカーシブルコール（再帰呼び出し）と言われる手法を使っていきます。

ユークリッド互除法

2つの整数の最大公約数を見つけるやりかた。2000年以上前にも遡ることが出来る最古のアルゴリズムだとか。

最大公約数とは

約数

ある自然数（0以上の整数）を割り切ることが出来る整数。

公約数

複数の自然数に共通の約数。

最大公約数

公約数の内最大のもの。

例）3と9の最大公約数は3。8と12の最大公約数は4。56と98の最大公約数は14。

ユークリッド互除法の考え方

a > bになる2つの整数a,bの最大公約数は、bとaをbで割った余りの最大公約数に等しい、という性質があります。
aをbで割った余りをrとして、上記の性質を利用すると、bをrで割った余りを求め、さらに r をその余りで割ったときの余り、と余りを求める計算を繰り返して、余りが 0 になった時の割った数（除数）がaとbとの最大公約数になる、という考え方が、ユークリッド互除法です。

• 例えば3と9のとき
  　a=9,b=3
  　a÷b　余り0
  　割った数bは3なので、最大公約数は3
• 8と12では
  　a=12,b=8
  　a÷b　余り4
  　r=4
  　b÷r　余り0
  　割った数4が最大公約数
• 56と98では
  　a=98,b=56
  　a÷b　余り42
  r=42
  　b÷r　余り14
  b=42,r=14
  　b÷r　余り0
  割った数14が最大公約数

3番目の例では3回割り算をしてますが、2回めと3回目は同じb÷rの計算をしてますね。1回目も同じ計算になるにはどうしたら良いでしょう。
そもそも、最初の1回目がa÷bなので、そのあとも同じになるように代入をします。
つまり、

• 8と12では
  　a=12,b=8
  　a÷b　余り4
  　a=b,b=余り
  　a÷b　余り0
  　割った数4が最大公約数
• 56と98では
  　a=98,b=56
  　a÷b　余り42
  a=b,b=余り
  　a÷b　余り14
  a=b,b=余り
  　a÷b　余り0
  割った数14が最大公約数

という形にするわけです。ただ、これだと余りが変数に割り当てられていないので、「bに余りが代入されている」ところからをスタートだと考えます。すると、

1. bが0ならばaが最大公約数
2. bが0でないならばaにbを、bにa÷bの余りを代入する
3. 1に戻る

という形にすることが出来ます。

「なんでまだ計算してないのに結果が入ってることになるの？」　と思われる方もいるでしょうけれど、この、初回の計算をしたとみなして始めるは、ロジックを考えるときによく使う手段です。この視点を取り入れるだけで、複数の処理をまとめることが出来るときがしばしばあるので、「そういうものか」と思ってもらえると良いです。

フローチャート1

さて、上に書いた3つの手順をフローチャートにしてみます。

…繰り返しの中でやっている作業をよく見てみましょう。
練習0のときに確認しましたが、変数は代入したら元の値は消えてしまいますよね。
ということは、

1. a ← b
2. b ← a ÷ bの余り
   1つ目の作業をしたあと、2つ目の作業をするときには、もうaの値はbの値で上書きされています。じゃあ、順番を逆にしたら？　…解決しませんね。

ということは、せっかくスッキリしたと思うのにやっぱりrが必要なんでしょうか。
いえいえ、これを解決する手段があります。

フローチャート2

これが、リカーシブルコール（再帰呼び出し）を使った処理です。gcdという処理の中から、再度gcdという処理を呼び出す、呼び出された処理は更にgcdを…と自分自身を呼び出し続けているものです。
変数のスコープは開始から終了までなので、呼び出すときのa,bと呼び出されるときのa,bは別物になります。なので、この書き方で先程の上書き問題が解消されるのです。

コードでは

C言語

int gcd(int a, int b)
{
    if(b == 0){
        return a;
    } else {
        return gcd(b, a%b);
    }
}

JavaScript

function gcd(a,b){
    if(b==0){
        return a;
    } else {
        return gcd (b, a%b);
    }
}

その他の言語

その他の言語では、最大公約数は最初からライブラリに用意されています（笑）

• Java
  　BigIntegerクラスドにgcdメソッドがあります
• Python
  　mathモジュールにgcd関数があります
• C++
  　C++17以降に、stdにgcd関数があります

なので、このあたりは調べてみてください。

まとめ

リカーシブルコールを使うと、繰り返しをシンプルにすることが出来ます。
知らないで初めてコードで目にするとびっくりすると思うので、ここで見慣れてもらえると良いと思います。