基本情報技術者を学習してる者です。写真はこの問題の模範回答なんですが、

Question

基本情報技術者を学習してる者です。写真はこの問題の模範回答なんですが、関数f(x,y)が次のとおり定義されているとき、f(775,527)の値は幾らか。ここで, x mod yはxをyで割った余りを返す。

f(x, y): if y = 0 then return x else return f(y, x mod y)

写真の赤線が引いてあるところを見て欲しいんですが、527はyのはずなのになぜxになってるんですか？

Answer 1

ユークリッドの互除法による 最大公約数の求め方のアルゴリズムですね。
ネットの世界では暗号で使われるアルゴリズムです。

y = 0 のときは return x
y ≠ 0 のときは return f(y,x mod y)
であるから

f(x , y)
に関して
f(775,527)
とすると
x = 775 , y = 527 で
y = 527 ≠ 0 であるから
f(527 , 775 mod 527) = f(527 , 248)

f(527 , 248)
とすると
x = 527 , y = 248 で
y = 248 ≠ 0 であるから
f(248 , 527 mod 248) = f(248 , 31)

f(248 , 31)
とすると
x = 248 , y = 31 で
y = 31 ≠ 0 であるから
f(31 , 248 mod 31) = f(31 , 0)

f(31 , 0)
とすると
x = 31 , y = 0 で
y = 0 であるから
x = 31
が reyrun となりこれで確定する。

つまり、これが 775 と 527 の最大公約数ということになる。

「ユークリッドの互除法」
あるいは正しくは
「拡張ユークリッドの互除法」
といいます。

最大公約数を求めるには素因数分解を行って最大公約数を求めることが教科書では学習する。
しかし、大きな桁の大きな素数の場合、最大公約数を素因数分解を使って求めるのは困難である。
そこで、素因数分解を必要としないユークリッドの互除法によって最大公約数を求める。

巨大な素数をあつかうRSA暗号などでは最小公倍数、最大公約数を使う場面があり、このアルゴリズムが利用される。

https://www2s.biglobe.ne.jp/~m_okada/chiebukuro/rsa/euclidean/

Answer 2

このようなアルゴリズムを再帰的アルゴリズムと言うのですが、
再帰的に関数が呼び出される際のxやyが固定の値ではないからです。
再度呼び出されるときに、改めてxとyが設定し直されます。

このアルゴリズムは、大雑把には、左右(xとy)の値をmod計算を含めて入れ替えながら計算しています。
お互いに入れ替えながらmod(一種の割り算(除算))をしているので、既に回答があるように互除法と呼ばれます。

Answer 3

f(527,248)では、yが248（0ではない）なので、f(y, x mod y)がリターン値になります。つまり、f(248, 527 mod 248)になると思います。

Answer 4

元のアルゴリズムはどうなっているの？
元の数字を指定した数で割って、順に値を小さくしていくようなアルゴリズムかと。
結果、数値を指定した進数に変換するとか？