特定の入力が与えられたときに非常に多くの回数自分自身を呼び出す再帰関数があります-これはまさにそれがすべきことです。関数が無限にループしていないことはわかっています。特定の数の呼び出しとオーバーフローに達するだけです。これがスタックに大量のメモリを配置することによる問題なのか、それとも呼び出し回数の通常の制限によるものなのかを知りたいです。明らかに、最大である特定の呼び出し数を言うのは非常に難しいですが、誰かが私に大まかな推定値を与えることができますか? 数千単位ですか？何百？何百万？
質問する
806 次
5 に答える
3
ご想像のとおり、問題は (同名の) スタック オーバーフローです。呼び出しごとに新しいスタック フレームを設定し、新しい情報をスタックにプッシュする必要があります。スタックサイズは固定され、最終的には不足します。
スタックサイズを設定するものは何ですか? これはコンパイラのプロパティです。つまり、バイナリ実行可能ファイルに対して固定されています。Microsoft のコンパイラ (VS2010 で使用) では、デフォルトで 1 メガバイトになり、コンパイラ オプションで "/F " で上書きできます ( '03 の例についてはこちらを参照してください。ただし、構文は同じです)。
実際に何回の呼び出しに相当するかを把握することは非常に困難です。関数のスタック サイズは、そのローカル変数、戻りアドレスのサイズ、およびパラメーターがどのように渡されるか (一部はスタックに入る可能性があります) によって決まり、その多くはアーキテクチャにも依存します。一般に、後者の 2 つは 100 バイト未満であると想定できます (これは概算です)。前者は、関数で何をしているかによって異なります。たとえば、関数がスタック上で 256 バイトを使用すると仮定すると、1M スタックでは、オーバーフローする前に 4096 回の関数呼び出しが発生しますが、メイン関数などのオーバーヘッドは考慮されていません。
ローカル変数とパラメーターのオーバーヘッドを削減しようとすることもできますが、実際の解決策は、再帰関数を呼び出すときにコンパイラーが呼び出し元の関数を解放する末尾呼び出しの最適化です。MSVC でこれを行う方法の詳細については、こちらを参照してください。テール コールを実行できず、スタック サイズを許容範囲内に縮小できない場合は、"/F" パラメーターを使用してスタック サイズを大きくするか、(推奨される解決策として) 再設計を検討できます。
于 2012-04-13T18:21:57.627 に答える
2
スタックで使用する情報の量に完全に依存します。ただし、Windows のデフォルト スタックは 1MB で、Unix のデフォルト スタックは 8MB です。単純に呼び出しを行うには、いくつかの 32 ビット レジスタと戻りアドレスをプッシュする必要があるため、1 回の呼び出しでおそらく 20 バイトを見ている可能性があり、空の関数の場合、Windows では最大で約 50k、Unix では 400k になります。
もちろん、私の知る限り、スタック サイズは変更できます。
于 2012-04-13T18:21:26.453 に答える
0
再帰関数によって使用されるスタックスペースの量は、再帰の深さと各呼び出しによって使用されるメモリスペースの量によって異なります。
再帰の深さは、任意の時点でアクティブなコールのレベルの数を指します。たとえば、バイナリツリーには、たとえば100万個のノードがある場合がありますが、バランスが取れていれば、同時にアクティブな呼び出しを20回以内でトラバースできます。バランスが悪い場合は、最大深度がはるかに大きくなる可能性があります。
各呼び出しで使用されるメモリの量は、再帰関数で宣言された変数の合計サイズによって異なります。
再帰の最大深度に固定の制限はありません。合計使用量がシステムによって課せられたスタック制限を超えると、スタックオーバーフローが発生します。
再帰の深さをなんらかの方法で減らすことによって、おそらくトラバースしているものを再構築することによって（それについてはあまり教えてくれませんでした）、または宣言されたローカルオブジェクトの合計サイズを減らすことによって、メモリ使用量を減らすことができるかもしれません再帰関数内（ヒープに割り当てられたオブジェクトはスタックサイズに寄与しないことに注意してください）、または2つの組み合わせ。
そして、他の人が言っているように、許可されたスタックサイズを増やすことができるかもしれませんが、それはおそらく限られた用途にすぎません-そしてそれはあなたがあなたのプログラムを実行する前にあなたがしなければならない余分なことです。また、リソースを消費し、システム上の他のプロセスに干渉する可能性があります（理由により制限が課せられます）。
再帰を回避するためにアルゴリズムを変更することは可能かもしれませんが、繰り返しになりますが、それについて多くを語るのに十分な情報がありません。
于 2012-04-13T19:32:02.187 に答える
0
選択肢の 1 つは、デフォルトのスタックサイズを変更または増やすことです。これが一つの方法です http://msdn.microsoft.com/en-us/library/tdkhxaks(v=vs.80).aspx
于 2012-04-13T18:11:05.220 に答える
0
スタック使用量を測定するツールがあります。事前に特定のバイト パターンでスタックを埋め、後で変更されたアドレスを調べます。それらを使用すると、限界にどれだけ近づくかを知ることができます。
おそらく、valgrind ツールの 1 つがそれを行うことができます。
于 2012-04-13T18:45:52.713 に答える