8

再帰的に自分自身を呼び出す関数があり、無限ループに入った場合、つまり同じ問題で再度呼び出された場合に検出して終了したいと考えています。それを行う最も簡単な方法は何ですか？

編集: これは関数であり、x と y の異なる値で再帰的に呼び出されます。再帰呼び出しで、ペア (x,y) の値が繰り返される場合に終了したい。

int fromPos(int [] arr, int x, int y)
4

11 に答える 11

11

関数が純粋関数型である場合、つまり状態や副作用がない場合はSet、呼び出された引数のaを保持できます（編集：編集を確認すると、（x、y）のペアのセットを保持します）。を使用して、毎回、現在の引数がセットに含まれているかどうかを確認します。そうすれば、サイクルにすぐに遭遇した場合に、サイクルを検出できます。ただし、引数スペースが大きく、繰り返しに到達するまでに長い時間がかかる場合は、サイクルを検出する前にメモリが不足する可能性があります。もちろん、これは停止性問題であるため、一般的にはそれを行うことはできません。

于 2009-06-23T03:56:43.343 に答える
4

あなたがそれを求めたように、一般的な解決策がないので、あなたは回避策を見つける必要があるでしょう。詳細については、停止問題を参照してください。

于 2009-06-23T04:01:53.373 に答える
2

プログラム分析を使用して、最も些細なものだけを検出できます。最善の方法は、特定の状況でガードを追加し、深度レベルのコンテキストを渡すことです。一般的なケースを検出し、再帰的アルゴリズムの正当な使用を区別することはほぼ不可能です。

于 2009-06-23T04:00:58.490 に答える
1

一貫性のあるシグニチャにオーバーロードを使用するか（これがより良い方法です）、静的変数を使用できます。

int someFunc(int foo)
{
    static recursionDepth = 0;
    recursionDepth++;
    if (recursionDepth > 10000)
    {
        recurisonDepth = 0;
        return -1;
    }
    if (foo < 1000)
        someFunc(foo + 3);
    recursionDepth = 0;
    return foo;
}

静的変数はそうではありませんが、スレッドセーフであるため、オーバーロードに関するJohnKugelmanの答えの方が優れています。

ビリー3

于 2009-06-23T04:05:31.750 に答える
0

メソッドシグネチャを保持したい場合は、xとyの古い値を記録するためにいくつかのセットを保持できます。

static Set<Integer> xs;
static Set<Integer> ys;//Initialize this!
static int n=0;//keeps the count function calls.

int fromPos(int [] arr, int x, int y){

 int newX= getX(x);
 int newY= getY(y);
 n++; 
 if ((!xs.add(Integer.valueOf(newX)) && !ys.add(Integer.valueOf(newY))){

   assert(n<threshold); //threshold defined elsewhere.
   fromPos(arr,newx,newy);
 }
}
于 2009-06-23T03:54:29.960 に答える
0

2Dアレイで作業しているようです。配列の値に余裕がある場合は、それをフラグとして使用できます。確認し、フラグが設定されている場合は再帰を終了してください。次に、続行する前に設定します。

値に余裕がない場合は、代わりにいつでもオブジェクトの配列にすることができます。

于 2009-06-23T03:59:27.947 に答える