Wie eine Endlosschleife in einem rekursiven Aufruf erkennen?

Question

Ich habe eine Funktion, die sich selbst rekursiv aufruft, und ich möchte, erkennen und zu beenden, wenn in eine Endlosschleife geht, das heißt - wieder für das gleiche Problem genannt zu werden. Was ist der einfachste Weg, das zu tun?

EDIT: Dies ist die Funktion, und es wird rekursiv mit unterschiedlichen Werten von x und y aufgerufen. Ich mag beenden, wenn in einem rekursiven Aufruf, der Wert des Paars (x, y) wiederholt.

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

Answer 1

Wenn die Funktion rein funktional, dh es keine staatlichen oder Nebenwirkungen hat, dann könnten Sie eine Set der Argumente halten (edit: Ihren bearbeiten sehen, würden Sie einen Satz von Paaren (x, y halten)), dass es wurde genannt, und jedes Mal nur prüfen, ob das aktuelle Argument in dem Satz ist. Auf diese Weise können Sie einen Zyklus erkennen, wenn Sie es laufen in ziemlich schnell. Aber wenn das Argument Raum groß ist und es dauert eine lange Zeit, um eine Wiederholung zu erhalten, können Sie Ihren Speicher aus, bevor Sie einen Zyklus erkennen. Im Allgemeinen natürlich, Sie können es nicht, weil dies das Halteproblem ist.

Answer 2

Eine Möglichkeit ist es, eine depth Variable von einem Aufruf zum nächsten weiterzugeben, es jedesmal, wenn Ihre Funktion sich selbst aufruft erhöht wird. Überprüfen Sie, dass depth wächst nicht größer als einem bestimmten Schwellenwert liegt. Beispiel:

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

Answer 3

Sie müssen eine Behelfslösung finden, weil, wie Sie es gefragt haben, gibt es keine allgemeine Lösung. Sehen Sie sich das Halting Problem für weitere Informationen.

Answer 4

Eine einfache Möglichkeit wäre eine der folgenden Möglichkeiten zu implementieren:

Führen Sie den vorherigen Wert und den neuen Wert auf den rekursiven Aufruf und machen Sie den ersten Schritt eine Überprüfung, um zu sehen, ob sie gleich sind -. Dies ist möglicherweise Ihr rekursive Fall

Übergeben Sie eine Variable, die die Anzahl von Malen, um anzuzeigen, die Funktion aufgerufen wurde, und willkürlich die Anzahl der Male beschränken sie aufgerufen werden kann.

Answer 5

Sie können nur erfassen die meisten trivialen Programmanalyse. Das Beste, was Sie tun können, ist Wächter in Ihren besonderen Umstand addieren und eine Tiefe Ebene Kontext passieren. Es ist fast unmöglich, den allgemeinen Fall zu erkennen und legitime Verwendung von rekursiven Algorithmen zu unterscheiden.

Answer 6

Sie können entweder für eine einheitliche Signatur Überlastung (dies ist die bessere Methode), oder Sie können eine statische Variable verwendet werden:

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 Antwort mit Überlastung ist besser beacuse es Thread-sicher ist, während statische Variablen nicht.

billy3

Answer 7

Sieht aus wie Sie auf einem 2D-Array arbeiten könnten. Wenn Sie ein zusätzliches Bit haben in den Werten des Arrays zu ersparen, können Sie es als ein Flag verwenden. Überprüfen Sie es, und beenden Sie die Rekursion, wenn das Flag gesetzt wurde. setzen sie dann, bevor es weiter.

Wenn Sie nicht etwas haben in den Werten zu ersparen, können Sie immer es stattdessen ein Array von Objekten machen.

Answer 8

Wenn Sie Ihre Methodensignatur behalten möchten, können Sie ein paar Sätze halten könnte alte Werte von x und y aufzunehmen.

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

Answer 9

IMHO Schleifen kann nur in eine Endlosschleife gehen.

Wenn Ihre Methode zu viele Ebene der Rekursion hat, wird die JVM eine Stackoverflow werfen. Sie können diesen Fehler mit mit einem try / catch-Block und tun, was Sie tun wollen, wenn dieser Zustand eintritt.

Answer 10

Eine rekursive Funktion beendet, falls eine Bedingung erfüllt ist.

Beispiele:

• Das Ergebnis einer Funktion ist 0 oder ist 1
• Die maximale Anzahl der Anrufe erreicht ist
• Das Ergebnis ist geringer / größer als der Eingangswert

In Ihrem Fall ist die Bedingung ([x0,y0] == [xN,yN]) OR ([x1,y1] == [xN,yN]) OR ([xN-1,yN-1] == [xN,yN])

0, 1, ...N sind die Indizes der Paare

So benötigen Sie einen Container (Vektor, Liste, Karte) alle bisherigen Paare zu speichern und sie an das Strompaar vergleichen.

Answer 11

Erster Einsatz mvn findbugs. Gui eine gui, die auf die Linie zu öffnen, in dem dieser Fehler vorhanden ist

Ich sah sich auch das gleiche Problem und ich löste es durch eine boolesche Variable in der Schleife Überprüfung hinzugefügt wird.

-Code vor ->

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

Um dieses Problem zu lösen, habe ich nur noch eine boolesche Variable und setzen Sie sich auf false im catch-Block. Prüfen Sie es nach unten

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

Dies ist, wie ich dieses Problem gelöst. Hoffe, dass dies helfen wird. :)