【C言語】再帰を用いるプログラムでのセグフォ

質問

明解C言語入門編のp196にあるList8-7
再帰を用いて２つの整数の最大公約数を求めるプログラムなんですが

#include<stdio.h>

int gcdf(int vx, int vy)
{
return(vy == 0? vx: gcdf(vy,vx&vy));
}

int gcd(int va, int vb)
{
return(va>vb? gcdf(va,vb): gcdf(vb,va));
}

としてmainの中で入力された２つの整数n1,n2を
最大公約数としてgcd(n1,n2)を表示させるのですが、
（１，２）とか（２，４）などの再帰が１度しか行われない（？）プログラムでは
ちゃんと結果が表示されるのですが、

（４，６）など再帰が２度以上行われるプログラムになると
segmentation fault(コアダンプ）
と表示されます。

どこに問題があるのでしょうか
OSはubuntu14.04
エディタはvim
コンパイラはclangです。

よろしくお願いします。

回答No.3

notnot · ベストアンサー

最大公約数はそもそもどうやって求めるか分かっていますか？
それとも単純にタイプミスでしょうか？

vx&vy
↓
vx%vy

なお、return の返値全体を括弧で囲むのは、文法間違いではありませんが、普通はしません。
なので、
return vy == 0 ? vx : gcdf(vy, vx % vy) ;

お礼

ありがとうやで

補足

申し訳ありませんタイプミスです。
vx%vyとした上で
大きな数値（２桁以上）を入力すると
すぐにセグフォが起こるのです。

回答No.6

Wap58

プリントしてセグフォを特定なのだ

#include<stdio.h>

int gcdf(int vx, int vy)
{
printf("gcdf vx %d vy %d\n",vx,vy);
return (vy==0? vx: gcdf(vy, vx%vy));
}

int gcd(int va, int vb)
{
printf("gcd va %d vb %d\n",va,vb);
return (va>vb? gcdf(va, vb): gcdf(vb, va));
}

回答No.5

notnot

＞vx%vyとした上で大きな数値（２桁以上）を入力するとすぐにセグフォが起こるのです。

ということであれば、書かれている範囲のプログラムにおかしい部分はないので、
書かれていない範囲のプログラムが間違っていると思います。
よく見直して下さい。

お礼

ありがとうございました

回答No.4

cametan_42

うーん、こちらだと特に問題ないんですけどねぇ。
Ubuntu 14.04LTSの64ビット、コンパイラは同じくclang使ってみましたが、2桁以上・・・まあ、このケースだと3桁でやってみましたが、セグフォは起きませんでした。

#include<stdio.h>

// ソースは同じ

int gcdf(int vx, int vy)
{
return (vy==0? vx: gcdf(vy, vx%vy));
}

int gcd(int va, int vb)
{
return (va>vb? gcdf(va, vb): gcdf(vb, va));
}

int main (void)
{
printf("%d\n", gcd(123, 456));
return 0;
}

// 実行

➜ OKwave clang List8-7.c
➜ OKwave ./a.out
12

// ここまで

まあ、「大きな数」ってのがどれくらい指すのか、って分からないと何とも言えないですけどねぇ。
もちろん、C言語なんかの場合、「int」が想定してる「最大の整数」を超えると挙動がおかしくなったりはするでしょう。
(Cの場合、最大の整数は32,767ですかね?)

なお、このソースの場合、Lispなんかやってる人だと当たり前の知識なんですが、「末尾再帰」と言うテクニックで記述されています。
末尾再帰ってのは、再帰で関数を呼び出す場合、その呼び出された関数に「余計な操作を加えてない」って意味ですね。

int gcdf(int vx, int vy)
{
return (vy==0? vx: gcdf(vy, vx%vy)); <- 条件によって、returnで呼び出される関数はgcdf「だけ」で、他にgcdf自体には余計な操作を加えていない。
}

さて、末尾再帰も再帰も原理的にはスタック(メモリ上の・・・簡単に言うと「関数呼び出し」の為の情報を保持しておく領域?)を消費して「効率が悪い」んですが、一方、末尾再帰の場合は、コンパイラの記述方法如何によっては「末尾再帰最適化」と言う技術が使われていて、末尾再帰で書かれたコードを単純なジャンプ構文に「自動変換」してくれて、スタックの消費を避けてくれます。
ありがたい事に、clangと言うコンパイラは末尾再帰最適化を行って、大変効率的なマシン語に落としてくれる模様です。
つまり、環境によるんですが、スタックを消費し過ぎた場合、セグメンテーションフォールトを起こす可能性がある、んですよねぇ。
clangで末尾再帰最適化を行う場合、コンパイル時点で -O3と言うオプショナル引数を与えます。
例えば、

clang -O3 自分で書いたソース

のように、ですね。
一回、このように、問題のソースを末尾再帰最適化を指定してコンパイルしてみて試してみて下さい。

回答No.2

cametan_42

int gcdf(int vx, int vy)
{
return(vy == 0? vx: gcdf(vy,vx&vy)); <- ココ
}

gcdfの第二引数で使われてる演算子が、&じゃなくって%にすべきなんじゃないですかね?

お礼

ありがとうやで

補足

申し訳ありませんタイプミスです。
vx%vyとした上で
大きな数値（２桁以上）を入力すると
すぐにセグフォが起こるのです。

回答No.1

Wap58

プリントすればわかります、無限ループになります。

わざと間違えて考えさせるソースなんでしょう

お礼

ありがとう