最大公約数を求める際に正しい答えが出ない

Question

再帰呼び出しとユークリッドの互除法を使って二つの正の整数a,bの最大公約数を求めるコードを作成したいです。

ユークリッドの互除法

1. a÷bの剰余をcとする
2. c=0ならば、最大公約数はbとなる（再帰打ち切り）
3. そうでなければ、func(b,c)が最大公約数となる（再帰呼び出し）

しかし以下のコードだと最大公約数が0だと表示されてしまいます。
なぜなのかを教えていただきたいです。

int func(int a, int b) {
	int c,ans;
    c=a%b;
    if (c==0) {
        ans=b;
        return ans;
    } else {
        func(b,c);
    }
}

int main() {
	int ans;
	int a=33, b=22;
	ans = func(a, b);
	printf("%dと%dの最大公約数は%d", a, b, ans);
	return 0;
}

Answer 1

int func(int a, int b) {
    int c, ans;
    c = a % b;
    if (c == 0) {
        ans = b;
        return ans;
    }
    else {
-        func(b, c); // ここreturnしていません
+        return func(b, c);
    }
}

Comments

[Red_Bull]

解くことができました。ありがとうございます！

なぜここにreturnがないといけないのかがわからないのですが、教えていただけないでしょうか...

[SHOMI]

return ans;
の方は理解できているのでしょうか？
再帰呼び出しかどうかは一旦脇においておいて、returnがないと呼び出し元に何を返せばよいか不明でしょう。

[Red_Bull]

return ansの方はmainに値を渡すので必要だと思うのですが、
return func(b, c)の方は再帰しなければいけないのでreturnは必要ないと思っていました。

[SHOMI]

>return ansの方はmainに値を渡すので必要だと思うのですが、
1回目に渡したaがbで割り切れる値でない場合(func(b, c)として呼ばれた場合)、値を返している先はmainではありません。
func(b, c)が返す先はそれを呼んだ再帰元のfuncに対してです。そのさらに呼び出し元へ値を返すためにはreturnが必要でしょう。
再帰かどうかなんて関係ありません。
下記のプログラムでb()をreturnなしにしたのと同じことです。
int a()
{
return 1;
}
int b()
{
return a();
}
int main()
{
int i = b();
return 0;
}

[littlestream]

横入失礼します。再起処理は自らの関数を呼び出すため、return して戻る条件がないと
最悪の場合、値が求められるどころかスタックオーバーフローしてしまい、エラーを起こします。
例として
a=4,b=8のとき、c=4&7=4,1回目
a=8,c(b)=4のとき、c=8&3=0,2回目
c=0ならば(b)=4が最大公約数になるはずですが、ある意味ループの脱出条件がないのと同じで
ずっと計算処理を行うことになり、正しい値が求められなくなるからです。

[SHOMI]

>a=4,b=8のとき
ユークリッドの互除法なのでa ≧ bという前提条件があるはずです。
呼び出し元で保証する前提なのでしょう。
とはいえ、スタックサイズの問題があるので再帰呼び出しは避けたいところですが。

[Red_Bull]

理解しました！ありがとうございます