Python(9)再帰のお勉強:ユークリッドの互除法

前の関連記事：Python(8)線形再帰を非再帰に変換する方法

前回再帰関数の動きを図にする方法がわかっただけでだいぶ理解が進みました。今度はいろいろ再帰関数の例を非再帰に変換してみます。

ユークリッドの互除法

ユークリッドの互除法とは自然数xとyの最大公約数を求める方法です。
$${\rm gcd}(x, y) = \begin{cases}
{\rm gcd}(y,  x \bmod y) & (y > 0)  \\
x & (y = 0)
\end{cases}$$
yが0になるまで関数gcd()を繰り返し実行していけば、最大公約数が求められます。

ということでこれは漸化式なので再帰で表現できます。

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
print(gcd(24, 9))

これを実行すると24と9の最大公約数3が出力されるはずです。

これは自分自身を呼び出したあとに何もしていませんので、末尾再帰になります。

def gcd(x, y):
    if y == 0:
        return x
    else:
        x %= y  # xをyで割った余りをxに代入。
        x, y = y, x  # xとyの中身を入れ換え。
        return gcd(x, y)
print(gcd(24, 9))

自分自身を呼び出しているとはっきりさせるために引数の中で計算しているのを外にだすとこんな感じになります。

return gcd(x, y)は何を返している？

7行目のgcd(x, y)をreturnしていますが、これは何を返しているのでしょう？

計算結果の「3」は3行目のreturn xで返されているはずです。

def gcd(x, y):
    if y == 0:
        return x
    else:
        x %= y
        x, y = y, x
        gcd(x, y)
print(gcd(24, 9)) 

試しにgcd(x, y)を返さずに実行すると「None」が返ってきます。

戻り値がないということです。

これは図に書いてみると理解できました。
return gcd(x, y)のreturnがないと4回目の戻り値xは3回目の呼び出し元に戻されるだけで1回目のところまでは戻ってきません。
return gcd(x, y)とすると、4回目のreturn xの戻り値が元の呼び出したところまでreturnをたどって元のgcd(x, y)まで戻ってきます。

このとき帰り道で、つまりgcd(x, y)を呼び出した後で、returnを実行していることになるので末尾再帰と言っていいのだろうか、と疑問に思ったのですが、どうもそれでよいようです。

末尾再帰の型にはめて再帰の除去をする

def foo(n):
    CODE_A
    if CONDITION_A:
        CODE_B
        foo(m)

Python(8)線形再帰を非再帰に変換する方法の末尾再帰のこの型にあてはめてみます。

def gcd(x, y):

    if y == 0: # CODE_A
        return x 

    if y > 0:  # CONDTION_A

        x %= y # CODE_B
        x, y = y, x 

        return gcd(x, y)

print(gcd(24, 9))

これは11行目で自分自身をそのままreturnしているので以下のように非再帰にできるはずです。

def foo(n):
    CODE A
    while CONDITION A:
        CODE_B
        CODE_A

ということでそれぞれ置き換えてみます。

def gcd(x, y):
    if y == 0:
        return x
    while y > 0:
        x %= y
        x, y = y, x
        if y == 0:
            return x
print(gcd(24, 9))

これで非再帰になります。

関数gcd()の引数x, yは自然数のみと考えると2行目のif文がTrueになることはないので省略できます。

def gcd(x, y):
    while y > 0:
        x %= y
        x, y = y, x
        if y == 0:
            return x
print(gcd(24, 9))

これで再帰の除去が完了です。まだ冗長な部分が残っていますけどね。
再帰を除去したwhile文は再帰で実行したものをつなげたものとわかります。

def gcd(x, y):
    while y > 0:
        x %= y
        x, y = y, x
    return x
print(gcd(24, 9))

while文を抜けたときはy==0に決まっているのでif y == 0:は略してこのように書けますね。

while文を書いているとwhileの前とwhileの中に同じコードがでてきてなんとかならないかな、と思ったことがあるのですが、それは再帰に変形できる場合で、このCODE_Aに相当する部分だったのかも。

次の関連記事:Python(10)再帰のお勉強:自然数の階乗