C言語関係掲示板

過去ログ

No.205.再帰関数の注意点


No.1281

関数の障害
投稿者---こ-いち(2002/03/19 01:08:53)


unsigned long int f (ensigned long int N)
{
unsigned long int M;
if (N==0){M=0;} else {M=N+f(N-1);}
return (M);
}

この関数に充分大きいNを代入して、もし障害が発生するとしたら
どんな障害が発生するかわかる方、教えてください。
お願いします。

No.1282

Re:関数の障害
投稿者---名前がかぶってしまいました(2002/03/19 01:39:19)


こーいちさん、ごめんなさい。
名前かぶってしまいました。ついうっかりおなじくしてしまいました。
すいません。。

No.1287

Re:関数の障害
投稿者---C職人(2002/03/19 09:16:57)


>こーいちさん、ごめんなさい。
>名前かぶってしまいました。ついうっかりおなじくしてしまいました。
>すいません。。

error C2177: 定数が大きすぎます
十分に大きな値を指定すると上記のようなエラーが発生しました。
unsigned long int で確保できる範囲を超えてしまったので
エラーとなります。


No.1288

Re:関数の障害
投稿者---ともじ(2002/03/19 10:37:14)


こんにちは。

>unsigned long int f (ensigned long int N)
>{
> unsigned long int M;
> if (N==0){M=0;} else {M=N+f(N-1);}
> return (M);
>}
>
>この関数に充分大きいNを代入して、もし障害が発生するとしたら
>どんな障害が発生するかわかる方、教えてください。
>お願いします。

このプログラムは再帰を使って、
 0+1+2+3+4+5+・・・+N
の計算をしています。

ですから、
 0+1+2+3+4+5+・・・+N
の計算結果が unsigned long int を越えてしまうようなNを
設定すると、オーバーフローが発生し、正常な解が得られません。

No.1289

Re:関数の障害
投稿者---B.Smith(2002/03/19 11:26:33)


こんにちは。

私の方から動作の面で少しだけお話しします。
unsigned long int f(unsigned long int N)
{
    unsigned long int M;

    if (N == 0){
        M = 0;
    } else {
        M = N + f(N - 1);
    }

    return (M);
}

関数が呼び出されると、スタック領域が使用されます。関数の引数、ローカル変数、それとソースからでは判りませんが、リターンアドレス等がスタックに積まれます(関数の引数に関してはコンパイラに依存する面があります)。関数が終了した時点で、使用していたスタックは元に戻ります。

今回の場合、再帰の回数分、関数で必要なスタック領域を確保することになります。スタックのサイズには限りがありますので、再帰の回数が非常に多いとスタックの使用限度を超えてしまうため、実行時にスタックオーバーフローになります。これを回避するためには、

・スタック使用量を減らす(再帰の削減、引数・ローカル変数の削減)
・スタックサイズを増やす

スタックサイズの変更は、リンカのスイッチにあるはずです。リファレンスマニュアルを参照してください。

再帰処理では、常にスタックサイズの問題が付き纏いますので注意してください。
最近のコンパイラでは、スタックをデフォルトで大きく確保している場合があるため、再帰の回数が少なければそれほど問題にはなりませんが、昔のコンパイラではメモリモデルの関係等から、スタックサイズを十分に確保することが出来ない場合があり、実行時にスタックオーバーフローという形でエラーを出すことがあります。

それと、余計なことかもしれませんが、一文字だけの関数名や変数名はなるべく避けた方が、後々作業で苦労せずに済みます。
一文字だけの関数名・変数名を使用しているプログラムは良く見かけますが、実際に大きなプログラムで使用すると、見辛くなるだけでなく、テキストエディタの検索や置換の使用が困難になってしまいます。できれば3文字以上の名前を付けた方がいいですね。



No.1291

Re:スタックオーバーフロー
投稿者---ともじ(2002/03/19 16:45:44)


B.Smithさん、いつもありがとうございます。

>今回の場合、再帰の回数分、関数で必要なスタック領域を確保することに
>なります。スタックのサイズには限りがありますので、再帰の回数が非常に
>多いとスタックの使用限度を超えてしまうため、実行時にスタックオーバー
>フローになります。

おっしゃる通りです。
課題の解答でしたら、私の書きこみでも良いと思いますが、実際に
動作させることを考えると、スタックオーバーフローの方が深刻ですね。
試しにLSIC86で実行してみたら、最初のプログラムは再帰を200
繰り返す前にオーバーフローしてしまいました。
変数がunsigend longにしろ、ここまで小さな値でオーバーフロー
したのには、いささか驚きました。

ところで、実行時のエラー回避ですが、
stackavail()などでスタックサイズを監視し、基準以下になったら、
exit(1)でも差し支えないのでしょうか。


No.1293

Re:スタックオーバーフロー
投稿者---B.Smith(2002/03/19 20:53:23)


いつもお世話になります。

>課題の解答でしたら、私の書きこみでも良いと思いますが、実際に
>動作させることを考えると、スタックオーバーフローの方が深刻ですね。

計算上のオーバーフローを知ることは大事ですから、ともじさん、C職人さんの方をメインに見てもらいたいですね。
今回、私の方は補助的な内容ですので、実際に実験した時、動作で問題が発生したら、その時は私の書き込みを参考にされると良いかもしれません。

>試しにLSIC86で実行してみたら、最初のプログラムは再帰を200
>繰り返す前にオーバーフローしてしまいました。
>変数がunsigend longにしろ、ここまで小さな値でオーバーフロー
>したのには、いささか驚きました。

ソースからある程度の予測は可能ですが、実際にはスタックが、関数が呼び出される前にも使用されている可能性はあります(例えば他の関数内から呼び出した場合等)。そのため、実行してみないと判らない部分はありますね。
見えない部分、コンパイル後のコード(Intel x86)では、CALL命令が行うスタック操作で、PCレジスタとCSレジスタをプッシュしますので4バイト必要になり、引数操作のためBPレジスタのプッシュでさらに2バイト必要になります。
勿論、これ以外にもPUSH命令が使用される可能性がありますから、実際の推測よりも小さい使用量でオーバーフローを起こします。通常は、コンパイル後のコードのことはあまり気にしないので、デバッグ時の頭痛のタネになります。

>ところで、実行時のエラー回避ですが、
>stackavail()などでスタックサイズを監視し、基準以下になったら、
>exit(1)でも差し支えないのでしょうか。

手持ちの資料でははっきりしたことが判らなかったので、Win2K、MS-DOS6.2/Vで実験してみました。関数exitで結果的にスタックは解放されているようですので、問題ないと思います。
私も知りたいので、はっきり分かる方、どうか教えてください。

exitの、このような使い方に関しては用途によると思います。ちょっとした実験での使用は問題ないと思いますが、実用品ではスタックオーバーフローの可能性があること自体が問題であり、またプログラムの都合で動作を停止させてはなりませんから、あまりこのような使い方はしないと思います。



No.1296

Re:スタックオーバーフロー
投稿者---ともじ(2002/03/20 00:49:50)


返信ありがとうございます。

>exitの、このような使い方に関しては用途によると思います。ちょっとした
>実験での使用は問題ないと思いますが、実用品ではスタックオーバーフロー
>の可能性があること自体が問題であり、またプログラムの都合で動作を停止
>させてはなりませんから、あまりこのような使い方はしないと思います。

実は動作確認をしようと、LSIC86でいきなりN:1000を設定したら、
みごとに暴走し、修復不可能になりました。
そこで思いついたのが、「stackavail()でスタックサイズを監視し、
基準以下になったら、exit(1)する」方法だったわけです。

実を言いますと、私は再帰そのものが好きではなく、自分でプログラム
を作るときに入れ込むことをしたことがありません。
学問上のCでは再帰もいいと思いますが、現場では再帰を使うメリット
よりデメリットの方が多いような気がします。
同様に複雑なマクロもプログラムが複雑になるだけのような気がして
使ったためしがありません。
それで、本編に再帰も関数型マクロの説明もないのです。
まあ、これはどうでもいい話ではありますが。


戻る


「初心者のためのポイント学習C言語」 Last modified:2002.05.26
Copyright(c) 2000-2002 TOMOJI All Rights Reserved