ユークリッド互除法を再帰関数で書いてみる

　ユークリッドの互除法とは、定理「a を b で割ったときの余りを r とすると《a と b の最大公約数》と《b と r の最大公約数》は一致する」を使って、下のような手順で《a と b の最大公約数〉を求める方法です。

 7298 ÷ 5963 ＝ 1 … 1335
　　↙︎　　　　↙︎
5963 ÷ 1335 ＝ 4 … 623
　　↙︎　　　 ↙︎
1335 ÷ 623 ＝ 2 … 89
　　↙︎　　　↙︎
623 ÷ 89 ＝ 7 … 0

　最後に余りが 0 になったときの b 、上の場合は 89 が《7298 と 5963 の最大公約数》です。
　さて、上のことを Python でコード化すると、

a=int(input("自然数を入力してください "))
b=int(input("自然数を入力してください "))
r=a%b          #　a%bは「aをbで割ったときの余り」
while r>0:     #　ここからループ始まり
    a=b
    b=r
    r=a%b      #　 ここでループ終わり
print("最大公約数は ", b)

となります。ところで、このコードは関数を定義して書くことも出来ます。以下、「２数 a , b の最大公約数を求める関数」をGCM(a,b) で表すことにします。そうすると、最初に書いた割り算の部分は、次のように書けます。

　　GCM(7298,5963)＝GCM(5963,1335)＝GCM(1335,623)
　　＝GCM(623,89)＝GCM(89,0) = 89

これを一般化して変数 a , b を使って書くと「GCM(a,b)＝GCM(b,a%b)」となります。これがいわゆる再帰関数です。そして最後に再帰から抜け出す部分が「もし b が 0 になったら、そのときの a が求める最大公約数」となるわけです。
　はい、準備が整いました。ユークリッドの互除法を再帰関数で書くと、こう（↓）なります。

　　def GCM(a,b):                        #　ここから関数定義
　　    if b==0:                         #　もし b が 0 なら
 　　       return a                          #　a を返す
　　    return GCM(b,a%b)                #　GCM(b,a%b) を返す

a=int(input("自然数を入力してください "))   #　ここからプログラム本体
b=int(input("自然数を入力してください "))
print("最大公約数は ", GCM(a,b))        #　ここで関数を呼び出す

　慣れないと難しいですが、出来上がったものを読むと、むしろとっても分かりやすい。それが再帰関数です。