c# - C# での再帰の使用

Question

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

score 33 · Accepted Answer

何回再帰できるかは、以下によって異なります。

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

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

score 8 · Accepted Answer

それは実際に使用している再帰的アルゴリズムに依存します。単純な再帰の場合は、次のように実行できます。

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);
}

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

score 3 · Accepted Answer

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

ほとんどの再帰的アルゴリズムは、反復的に表現できます。

割り当てられたスタックスペースを増やすにはさまざまな方法がありますが、最初に反復バージョンを見つけてみましょう。:)

score 1 · Accepted Answer

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

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

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

score 1 · Accepted Answer

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

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

score 1 · Accepted Answer

これについての短い記事をここに書きました。基本的に、深さというオプションのパラメーターを渡し、深く掘り下げるたびに 1 を追加します。再帰メソッド内で、値の深さを確認します。設定した値よりも大きい場合は、例外をスローします。値 (しきい値) は、アプリケーションのニーズによって異なります。

score 0 · Accepted Answer

システムの制限について尋ねなければならない場合は、おそらく何かひどく間違ったことをしている可能性があることを忘れないでください.

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

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

c# - C# での再帰の使用

10 に答える 10

Related

Reference