C＃で再帰を使用する

StackOverflow https://stackoverflow.com/questions/610743

  •  03-07-2019
  •  | 
  •  

質問

スタックオーバーフローを回避する方法について再帰を使用する場合の一般的なルールはありますか？

役に立ちましたか？

解決

再帰を実行できる回数は、次の条件によって異なります。

  • スタックサイズ（通常は1MB IIRCですが、バイナリは手動で編集できます。そうすることはお勧めしません）
  • 再帰の各レベルが使用するスタックの量（10個のキャプチャされていない Guid ローカル変数を持つメソッドは、たとえばローカル変数を持たないメソッドよりも多くのスタックを使用します）
  • 使用しているJIT-JITは末尾再帰を使用する場合があります 、そうでない場合もあります。ルールは複雑で、覚えられません。 （ 2007年からのDavid Bromanによるブログ投稿、および同じ著者/日付のMSDNページですが、今は古くなっている可能性があります。）

スタックオーバーフローを回避する方法あまり遠くまで再帰しないでください:)遠くまで行かずに再帰が終了することを合理的に確信できない場合（「10以上」で心配ですが、それは非常に安全ですが）、再帰を避けるために書き直してください。

他のヒント

実際に使用している再帰アルゴリズムに依存します。単純な再帰であれば、次のようなことができます：

public int CalculateSomethingRecursively(int someNumber)
{
    return doSomethingRecursively(someNumber, 0);
}

private int doSomethingRecursively(int someNumber, int level)
{
    if (level >= MAX_LEVEL || !shouldKeepCalculating(someNumber))
        return someNumber;
    return doSomethingRecursively(someNumber, level + 1);
}

このアプローチは、再帰のレベルを論理的な制限として定義できる場合にのみ実際に役立つことに注意してください。これが発生しない場合（分割統治アルゴリズムなど）、単純さとパフォーマンスとリソースの制限のバランスをどのようにするかを決定する必要があります。これらの場合、事前に定義された任意の制限に達したら、メソッドを切り替える必要があります。クイックソートアルゴリズムでこれを使用した効果的な方法は、リストの合計サイズの比率として行うことです。この場合、論理的な制限は、条件が最適でなくなったときの結果です。

スタックオーバーフローを回避するためのハードセットについては知りません。私は個人的に-
1.基本ケースが正しい。
2.コードは、ある時点でベースケースに到達します。

それほど多くのスタックフレームを生成している場合は、再帰を展開してループにすることを検討してください。

特に、複数レベルの再帰（A-＆gt; B-＆gt; C-＆gt; A-＆gt; B ...）を実行している場合、これらのレベルの1つをループに抽出して保存できることがわかります。あなた自身にいくつかの記憶。

通常の制限は、連続する呼び出し間でスタックにあまり残っていない場合、約15000〜25000レベルの深さです。 IIS 6+を使用している場合、その25％。

ほとんどの再帰アルゴリズムは繰り返し表現できます。

割り当てられたスタック領域を増やすにはさまざまな方法がありますが、最初に反復バージョンを探してみましょう。 ：）

合理的なスタックサイズを確保し、問題を分割して克服することで、実際にはそうではなく、より小さな問題に継続的に取り組むことができます。

末尾再帰について考えたところですが、C＃はそれをサポートしていないことが判明しました。ただし、.Net-Frameworkはそれをサポートしているようです：

http：// blogs .msdn.com / abhinaba / archive / 2007/07/27 / tail-recursion-on-net.aspx

デフォルトのCLRで実行している場合、スレッドのデフォルトのスタックサイズは1 MBです。ただし、他のホストがそれを変更する場合があります。たとえば、ASPホストはデフォルトを256 KBに変更します。これは、VSの下で完全に実行されるコードがあるかもしれないが、実際のホスティング環境にデプロイすると壊れる可能性があることを意味します。

幸いなことに、正しいコンストラクタを使用して新しいスレッドを作成するときに、スタックサイズを指定できます。私の経験ではそれはめったに必要ではありませんが、これが解決策であるケースを見てきました。

バイナリ自体のPEヘッダーを編集して、デフォルトのサイズを変更できます。これは、メインスレッドのサイズを変更する場合に便利です。それ以外の場合は、スレッドを作成するときに適切なコンストラクタを使用することをお勧めします。

このこちら。基本的には、depthと呼ばれるオプションのパラメーターを渡し、さらに深くなるたびに1を追加します。再帰的メソッド内で、値の深さをチェックします。設定した値よりも大きい場合、例外をスローします。値（しきい値）は、アプリケーションのニーズに依存します。

システムの制限について尋ねる必要がある場合、恐らく恐ろしく間違ったことをしていることに注意してください。

したがって、通常の操作でスタックオーバーフローが発生する可能性があると思われる場合は、問題に対する別のアプローチを考える必要があります。

特にC＃にはGeneric :: Stackコレクションがあるため、再帰関数を反復関数に変換することは難しくありません。 Stackタイプを使用すると、使用されているメモリがスタックではなくプログラムのヒープに移動します。これにより、再帰的なデータを保存するための完全なアドレス範囲が得られます。それだけでは不十分な場合、データをディスクにページングすることはそれほど難しくありません。しかし、この段階に到達したら、他のソリューションを真剣に検討します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top