2 
class Program  
{
    static void Main(string[] args)
    {
        Test(0);
    }

    static void Test(int i)
    {
        if (i > 30000)
        {
            return;
        }
        Test(i + 1);
    }
}

上記のサンプルを呼び出すと、再帰関数を取得して StackOverflowException をスローするのはなぜですか。

（デフォルトの再帰スタックサイズを超えているため？）

しかし、私はこの問題をどのように解決するのだろうか.

ありがとう。

4

5 に答える 5

6

30,000 スタック フレームはかなり大きな数であるため、例外が発生します :-)

より慎重な方法で再帰を使用して解決します。再帰的に解決される理想的な問題は、「検索スペース」をすばやく削減する問題です(a)。

たとえば、再帰するたびに検索スペースが半分になる二分木トラバーサル:

def find (searchkey, node):
    if node = NULL:
        return NULL
    if searchkey = node.key:
        return node
    if searchkey < node.key:
        return find (searchkey, node.left)
    return find (searchkey, node.right)

2 つの符号なし整数 (および上記の独自のアルゴリズム) を追加することは、結果が計算されるずっと前にスタック割り当てを吹き飛ばしてしまうため、再帰には適していません。

def add (a, b):
    if a = 0:
        return b
    return add (a-1, b+1)

(a)検索空間は、考えられる答えのセット全体として定義できます。できるだけ早く減らしたい。

余談ですが、再帰の理想的な問題は、理論的/数学的な意味でスタックスペースとは何の関係もありません。それらは、次のように表現できる問題です。

  • 「より単純な」引数を使用した同じまたは類似の問題。
  • 「最も単純な」引数を持つ終了条件。

(この意味での「シンプル」は、終了条件に近づくことを意味します)。

理論的/数学的アプローチでは、スタック スペースを考慮する必要はありませんが、コンピューター サイエンティストとして考慮する必要があります。現実は限界を設定します:-)

再帰を使用しない場合も参照してください。再帰を反復に変換する状況。

于 2011-09-24T23:23:48.523 に答える
5

問題は、再帰が多すぎることです。非常に多くのレベルの再帰を使用する何をしていても、代わりにループを使用して解決する必要があります。

再帰で機能するアルゴリズムは、アイテムごとに 1 レベルの再帰を使用しません。通常、各レベルで作業を半分に分割するため、30000 項目の再帰は 15 レベルだけで済みます。

于 2011-09-24T23:23:10.597 に答える
2

StackOverflowExceptionへの 30k 呼び出し内のどこかでスタックがオーバーフローするため、 が発生していますTest。問題を「解決」する方法はありません。スタック サイズは制限されています (また、かなり小さい)。反復的に機能するようにコードを再設計できます。

for( int i = 0; i <= 30000; ++i )
{
    Test( i );
}

ただし、実際のユースケースはそれよりも複雑であると思います。それ以外の場合、再帰からの利益はありません。

于 2011-09-24T23:23:15.510 に答える
2

新しいスレッドのスタック サイズを手動で指定することもできますが、私はStack<T>またはループを使用します (単純化された例に必要なのはこれだけです)。つまり、再帰はまったく必要ありません。

Stack<int> stack = new Stack<int>();
stack.Push(1);
while(stack.Count > 0)
{
    int someValue = stack.Pop();
    //some calculation based on someValue
    if(someValue < 30000)
        stack.Push(someValue +1);
}
于 2011-09-24T23:27:18.747 に答える
1

この質問を見てください:再帰から反復への道

再帰が 30k+ レベルの深さになる場合は、おそらくそれを反復アルゴリズムに変えたいと思うでしょう。その質問の答えが役立つはずです。

于 2011-09-24T23:26:16.650 に答える