質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.02%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

Q&A

解決済

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

Red_Bull
Red_Bull

総合スコア19

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

1回答

0グッド

0クリップ

543閲覧

投稿2021/06/30 12:50

編集2021/06/30 13:25

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

ユークリッドの互除法

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

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

c

1int func(int a, int b) { 2 int c,ans; 3 c=a%b; 4 if (c==0) { 5 ans=b; 6 return ans; 7 } else { 8 func(b,c); 9 } 10} 11 12int main() { 13 int ans; 14 int a=33, b=22; 15 ans = func(a, b); 16 printf("%dと%dの最大公約数は%d", a, b, ans); 17 return 0; 18}

以下のような質問にはグッドを送りましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

グッドが多くついた質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

回答1

0

ベストアンサー

diff

1int func(int a, int b) { 2 int c, ans; 3 c = a % b; 4 if (c == 0) { 5 ans = b; 6 return ans; 7 } 8 else { 9- func(b, c); // ここreturnしていません 10+ return func(b, c); 11 } 12}

投稿2021/06/30 12:54

編集2021/06/30 12:55
SHOMI

総合スコア4079

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

Red_Bull

2021/06/30 12:58

解くことができました。ありがとうございます! なぜここにreturnがないといけないのかがわからないのですが、教えていただけないでしょうか...
SHOMI

2021/06/30 13:03

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

2021/06/30 13:06

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

2021/06/30 13:15 編集

>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

2021/06/30 13:15

横入失礼します。再起処理は自らの関数を呼び出すため、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

2021/06/30 13:22 編集

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

2021/06/30 13:23

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

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

再帰

情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。