最大公約数と最小公倍数の問題 php

質問

<?php
while(fscanf(STDIN, "%d %d", $a, $b)) {
$gcd = _gcd($a, $b);
$lcm = $a / $gcd * $b;
print $gcd . " " . $lcm . "\n";
}

function _gcd($a, $b) {
if($b == 0) return $a;
return _gcd($b, $a % $b);
}
?>

この部分の処理が理解ができません。
return _gcd($b, $a % $b);
$bに６、$aに８が入っていた場合、
ここは、何を返すのでしょうか？
よろしくお願いします。

回答No.3

superside0 · ベストアンサー

まず、$a % $b 　は、　$aを$bで割った余りです。例えば、8 % 6 の結果は　 2です。

そして、function _gcd のなかでは、 $bを$a に入れ替え, $aを$bで割った余りを$bとしながら、
$bが0になるまで、_gcdの呼び出しを繰り返しています。

このように、自分自身を呼び出すことを再帰的アルゴリズムというのですが、
このケースならば、whileループでも記載でき
function _gcd($a, $b ) {
　while ( $b != 0 ) {
　　$w = $b;　//$b値を一旦確保
　　$b = $a % $b;　//$aと$bで割った余りを$bへ代入
　　$a = $w; //剰余する前の$b値を$aへ代入
　}
　return $a;
}
と書くこともできます。

お礼

ご丁寧に対応していただいて、ありがとうございます。
とても、分かりやすかったです。
親切にありがとうございます。

回答No.2

f272

_gcd(6, 8%6)=_gcd(6, 2)=_gcd(2, 6%2)=_gcd(2, 0)=2
再帰的に処理されます。

お礼

再帰的に処理されるんですね。
ありがとうございます。

回答No.1

notnot

6 と 8%6 つまり、6 と 2 の最大公約数を返します。

お礼

ありがとうございます。