再帰呼び出しで無限ループを検出する方法は？

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

  •  06-07-2019
  •  | 
  •  

質問

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

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

int fromPos(int [] arr, int x, int y)
役に立ちましたか？

解決

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

他のヒント

1つの方法は、ある呼び出しから次の呼び出しに depth 変数を渡し、関数がそれ自体を呼び出すたびに増分することです。 depth が特定のしきい値より大きくならないことを確認します。例：

int fromPos(int [] arr, int x, int y)
{
    return fromPos(arr, x, y, 0);
}

int fromPos(int [] arr, int x, int y, int depth)
{
    assert(depth < 10000);

    // Do stuff

    if (condition)
        return fromPos(arr, x+1, y+1, depth + 1);
    else
        return 0;
}

尋ねたように、一般的な解決策がないため、回避策を見つける必要があります。詳細については、停止の問題をご覧ください。

簡単な方法は、次のいずれかを実装することです。

以前の値と新しい値を再帰呼び出しに渡し、最初のステップで同じかどうかを確認します-これはおそらく再帰的なケースです。

関数を呼び出した回数を示す変数を渡し、呼び出し可能な回数を任意に制限します。

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

一貫性のある署名のためにオーバーロードを使用するか（これがより良い方法です）、または静的変数を使用できます：

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

John Kugelmanのオーバーロードに関する答えは、スレッドセーフであるため、静的変数はそうではないためです。

Billy3

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

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

メソッドシグネチャを保持したい場合は、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);
 }
}

IMHOループのみが無限ループに入ることができます。

メソッドの再帰レベルが多すぎる場合、JVMはStackOverflowErrorをスローします。 try / catchブロックを使用してこのエラーをトラップし、この状態が発生したときに実行する予定の操作を実行できます。

条件が満たされた場合、再帰関数は終了します。

例：

  • 関数の結果は 0 または 1
    • です
  • 呼び出しの最大数に達しました
  • 結果は入力値より低い/大きい

あなたの場合、条件は（[x0、y0] == [xN、yN]）OR（[x1、y1] == [xN、yN]）OR（[xN-1、yN- 1] == [xN、yN]）

0、1、... N はペアのインデックスです

したがって、以前のすべてのペアを保存し、それらを現在のペアと比較するには、コンテナ（ベクター、リスト、マップ）が必要です。

最初にmvn findbugs：guiを使用して、このエラーが存在する行を指すGUIを開きます。

私も同じ問題に直面し、ループ検証にブール変数を追加することで解決しました。

前のコード-＆gt; 

for (local = 0; local < heightOfDiv; local = local + 200) { // Line under Error
          tileInfo = appender.append(tileInfo).append(local).toString();
          while (true) {
            try {
              tileInfo = appender.append(tileInfo).append(getTheTextOfTheElement(getTheXpathOfTile(incr))).toString();
              incr++;
            } catch (Exception e) {
              incr = 1;
              tileInfo = appender.append(tileInfo).append("/n").toString();
            }
          }

この問題を解決するために、catchブロックでブール変数を追加してfalseに設定しました。確認してください

for (local = 0; local < heightOfDiv; local = local + 200) {
          tileInfo = appender.append(tileInfo).append(local).toString();
          boolean terminationStatus = true;
          while (terminationStatus) {
            try {
              tileInfo = appender.append(tileInfo).append(getTheTextOfTheElement(getTheXpathOfTile(incr))).toString();
              incr++;
            } catch (Exception e) {
              incr = 1;
              tileInfo = appender.append(tileInfo).append("/n").toString();
              terminationStatus = false;
            }
          }

これは、この問題の解決方法です。 これが役立つことを願っています。 ：）

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