No.3ベストアンサー
- 回答日時:
再帰では、複雑な処理を簡潔に書けて、良いように思えますが、スタックオーバーフローの危険性を常に考慮すべきです。
スタック領域を消費するのは、ローカル変数の他、関数の引数、戻り値等です。また、ポインタ変数もスタックを使用しますので、いくら使用するメモリを動的に割り当てたとしても、ポインタ変数分のスタックメモリ(4バイト)は消費されます。
スタックオーバーフローを起こさないためには、再帰呼び出しの回数を制限するなどする必要がありますが、制限してしまっては、処理が完結しないこともあります。
このような場合には、再帰以外の方法を検討する必要があります。
forやwhileループを使用して、同じ処理が実現できないか検討してみましょう。
staticなポインタに動的にメモリを割り当てる方法を使用すれば、有る程度スタックオーバーフローの発生を遅らせることができますが、気をつけなければならないことがあります。
static変数は、その関数内でいつでも同じメモリ領域を使用するようになりますので、以下のようにする必要があります。
// 良い例
void func()
{
static int* i = new int;
// ここで何か処理をする
delete i;
func();
}
以下のようにすると、駄目です。
deleteで削除されるべきアドレスが、再帰先で上書きされてしまうためです。
// 駄目な例
void func()
{
static int* i = new int;
// ここで何か処理をする
func();
delete i;
}
また、こうしたところで、関数の呼び出しには、必ずスタックが消費されますので、完全にスタックオーバーフローを阻止することはできません。
再帰を使用しないアルゴリズムを考えましょう。
No.4
- 回答日時:
↓に追加です。
再帰関数に引数をつけているなら、引数をやめてしまって、static変数で次の再帰関数に値を伝える方法もできますね。通常の引数とはちょっと勝手が違いますが、スタックオーバーフローは延期できると思います。
また、戻り値も同様に、voidにして戻り値用のstatic変数を用意すればよいと思います。
ただ、staticは、通常のローカル変数とは勝手が違いますから、注意が必要です。
ちなみに、この場合、再帰に突入するコールで引数を渡せない&戻り値を受け取れない、という問題が発生します。なので、もしやるとすると、モジュールレベル変数を使用した方がよいかもしれません。
、、、やればやるほど複雑怪奇になり、「再帰=きれいに書ける」の定理が崩れてきますので、再帰をなくす方向がおすすめです。
回答ありがとうございます。
私の知りたいことが簡潔に書かれていて大変参考になりました。
再帰を用いないプログラムを考え直すことにします。
ありがとうございました。
No.2
- 回答日時:
記憶が曖昧ですが、VC++6.0の生成するスタックチェックコードは、一度に64KB以上くらいの大きさを確保すると、エラーを出すようになっていたはずです。
OS依存だと思いますが、それより小さいサイズを確保していくぶんには、デフォルトのスタック(1MB程度?)を使い切ったとしてもヒープと同じように自動的にサイズが増えていくので問題になることは少ないでしょう。
再帰かどうかは関係ないですが、関数を呼び出したときに、引数、ベースポインタ、戻りアドレス、呼び出し先関数の自動変数の合計サイズぶんのスタックが使用されます。普通に数十レベルくらいネストしても気にする程ではありません。
void recursiveFunction(int n)
{
char buff[256];
if (n < 100) {
recursiveFunction(n + 1);
}
}
int main()
{
recursiveFunction(0);
return 0;
}
↑くらいのネストなら「深刻」とは言えないです。
もっと巨大な領域を確保する必要があるなら、
struct MyDataType
{
char c[10000];
int n[1000];
double f[2000];
};
void recursiveFunction(int n)
{
MyDataType *p = new MyDataType;
if (n < 100) {
recursiveFunction(n + 1);
}
delete p;
}
↑のようにnewを使えばいいと思います。
この回答への補足
ご回答ありがとうございます。
上のnewを用いたプログラムでは、
MyDataType型のポインタpは使われているのですか?
私も上記のようなnewを用いた再帰関数を試してみたのですが、
やはりスタックオーバーフローで止まってしまいました。
やはり、ネストが深すぎるのでしょうか?
No.1
- 回答日時:
こんにちは。
関数で使うローカルな変数は、別の関数を呼び出すときにすべてスタックに積まれます。つまり、ローカル変数が多くて(領域が大きければなお効果的)、関数呼び出しのネストが深いと、再帰呼び出しでなくてもスタックオーバーフローをおこします。再帰呼び出しでは、気をつけないと呼び出しが何重にもなり、スタックオーバーフローをおこしやすい、ということです。
このことは、人間が処理の流れを目で追いかけることに喩えるとよくわかると思います。あなたの頭は、いくつの呼び出しを覚えていられますか?覚えられなくなった時点であなたのスタックがオーバーフローしたことになります。
関数中でstatic宣言すると、次の呼び出しで以前の内容は消えてしまいます。
main() {
recallFunc();
}
recallFunc() {
static int i = 1;
printf("i = %d\n", i++);
recallFunc();
}
さて、結果はどうなるでしょう?
この回答への補足
回答ありがとうございます。
なるほど、おそらく理解しました。
staticな変数を用いた再帰呼び出しでは、
処理がうまく行えないですね。
Heap領域のみを使えば問題ないのでしょうか?
それでもやはり、ネストが深いとスタックオーバーフローになってしまうんでしょうか?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(プログラミング・Web制作) 十進BASICでの再帰についての質問です。 2 2022/11/18 09:17
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- C言語・C++・C# C言語初心者 ポインタについて、お助けください、、 2 2023/03/15 23:50
- C言語・C++・C# スタックフレームの消滅 6 2023/05/20 12:33
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- C言語・C++・C# 至急教えてください!プログラミングの問題です。 割られる整数と割る整数を受け取って、商と余りを出力す 3 2022/07/05 10:23
- その他(プログラミング・Web制作) pythonのグローバル変数 2 2022/11/25 18:02
- C言語・C++・C# C言語 3 2022/10/04 15:07
- Java javaでのプログラム(配列)について質問です. 2 2022/10/14 22:27
- C言語・C++・C# C言語のwhileを含む関数について 2 2022/12/16 12:28
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
Cプログラミングの関数電卓のア...
-
最大スタックサイズを大きくす...
-
VB.netでDLLを読み込んで実行す...
-
ポインタ版リスト構造によるス...
-
エラー?メッセージ
-
基本情報技術者のデータ構造あ...
-
キューとスタックの問題です、...
-
プログラムの規模を表す単位「k...
-
タッチタイプの拗音が苦手です...
-
hdmiはパラレル?シリアル?
-
TCPではなく、UDPが音声や動画...
-
ステップ数??
-
ubuntuで デイスク/deb/loopと...
-
ライン数とステップ数の違いに...
-
ステップ数について
-
社内LANのネットワークトラフィ...
-
MoveNextの処理速度は?
-
[ASP]If~Else If~End If 対 Case
-
ネットワークの問題の解き方を...
-
「ByRef引数の型が一致しません...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
VB.netでDLLを読み込んで実行す...
-
最大スタックサイズを大きくす...
-
エラー?メッセージ
-
printf / sprintf のスタック消...
-
_CRTIMPの意味は?
-
スタックを用いて整数配列を入...
-
スタックフレームの消滅
-
関数呼び出しでのスタック消費量
-
逆ポーランド記法
-
スタックの伸張方向
-
スタック領域変更
-
関数のプロローグとエピローグ...
-
スタックとキューの使い所
-
再帰処理を非再帰処理に書き換...
-
CASLとCASL2の違いについて
-
Ethernetヘッダの取得 NDIS
-
VC++6.0 Stack Overflow !!
-
マス目上の移動のアルゴリズム
-
VCでのスタックサイズ
-
コンパイラオプション
おすすめ情報