wake-up-neo.com

Ausbruch einer Rekursion in Java

Die Rekursion ist eine Art "Teilen und Erobern" -Stil, sie teilt sich auf, während sie kleiner wird (Baumdatenstruktur), und ich möchte, dass sie vollständig bricht, wenn eine Verletzung gefunden wird, was bedeutet, dass alle rekursiven Pfade abgebrochen werden und true zurückgegeben wird. Ist das möglich?

22
Stasis

Sie können einen Fehlercode zurückgeben oder eine globale Variable ändern, so dass jede rekursive Instanz weiß, dass sie sich selbst abbricht.

Etwas von der Art.

int foo(bar){
     int to_the_next;

      if (go_recursive){
            to_the_next = foo(whisky_bar);

            if (to_the_next ==DIE) return DIE;
      }

      if (something_unexpected_happened) return DIE;

      process;//may include some other recursive calls, etc etc
}
15
Tom

Egal was Sie tun, Sie müssen den Stapel abwickeln. Dies lässt zwei Optionen übrig:

  1. Magischer Rückgabewert (wie von einem der Toms beschrieben)
  2. Eine Ausnahme auslösen (wie von Thaggie erwähnt)

Wenn der Fall, dass Dinge sterben sollen, selten ist, kann dies eine der Situationen sein, in denen das Auslösen einer Ausnahme eine praktikable Wahl sein kann. Und bevor sich alle dabei in den Hals springen, denken Sie daran, dass eine der wichtigsten Regeln der Programmierung das Wissen ist, wann es angebracht ist, die Regel zu brechen.

Wie sich herausstellte, habe ich heute die zxing-Bibliothek anhand von Google-Code bewertet. Sie verwenden tatsächlich Ausnahmen für viele Kontrollstrukturen. Mein erster Eindruck, als ich es sah, war Horror. Sie riefen buchstäblich Zehntausende Male mit unterschiedlichen Parametern, bis die Methode keine Ausnahme auslöst.

Das sah sicherlich nach einem Performance-Problem aus, daher habe ich ein paar Anpassungen vorgenommen, um den magischen Rückgabewert zu verwenden. Und weisst du was? Der Code war in einem Debugger um 40% schneller. Als ich auf Nicht-Debugging umgestiegen bin, war der Code weniger als 1% schneller.

Ich bin immer noch nicht begeistert von der Entscheidung, in diesem Fall Ausnahmen für die Flusskontrolle zu verwenden (ich meine, die Ausnahmen werden geworfen alle die Zeit). Aber es lohnt sich auf keinen Fall, es aufgrund des fast unermesslichen Leistungsunterschieds neu zu implementieren.

Wenn Ihre Bedingung, die den Tod der Iteration auslöst, kein wesentlicher Bestandteil des Algorithmus ist, kann die Verwendung einer Ausnahme den Code viel sauberer machen. Für mich ist der Punkt, an dem ich diese Entscheidung treffen würde, wenn die gesamte Rekursion abgewickelt werden muss, dann würde ich eine Ausnahme verwenden. Wenn nur ein Teil der Rekursion abgewickelt werden muss, verwenden Sie einen magischen Rückgabewert.

36
Kevin Day

Wenn es sich um einen einzelnen Thread handelt, der die Rekursion durchführt, könnten Sie eine Ausnahme auslösen.

boolean myPublicWrapperMethod(...) {
    try {
        return myPrivateRecursiveFunction(...);
    } catch (MySpecificException e) {
        return true;
    } 
} 

Ein besserer Ansatz wäre, die Rekursion zu beseitigen und eine Stack-Auflistung zu verwenden, die eine Klasse enthält, die den rekursiven Zustand darstellt, in einer Schleife durchlaufen wird und nur dann true zurückgibt, wenn Sie möchten.

5
Tom

Ich würde eine Ausnahmebehandlung empfehlen. Das macht deutlich, dass die Rekursion wegen einer Verletzung (oder einer anderen Ausnahme) abgebrochen wurde:

public void outer() {
  try {
    int i = recurse(0);
  } catch (OuchException ouch) {
    // handle the exception here
  }
}

private int recurse(int i) throws OuchException {

    // for tree-like structures
    if (thisIsALeaf) {
       return i;
    }

    // the violation test
    if (itHurts)
       throw new OuchException("That really hurts");

    // we also can encapsulate other exceptions
    try {
       someMethod();
    } catch (Exception oops) {
       throw new OuchException(oops);
    }

    // recurse
    return recurse(i++);
}

Sicher, es verstößt gegen die anfängliche Anforderung, bei der Abtreibung "wahr" zurückzugeben. Ich bevorzuge jedoch eine saubere Trennung der Rückgabewerte und eine Benachrichtigung über abnormales Verhalten.

4
Andreas_D

Sie können etwas Ähnliches tun, indem Sie eine Variable speichern, die verfolgt, ob die Rekursionen unterbrochen werden sollen oder nicht. Sie müssten es leider jede Rekursion überprüfen, aber Sie können es tun.

1
Joe Phillips

Sie fragen nach der Definition der Rekursion.

Irgendwann sollten alle rekursiven Pfade unterbrochen werden. Andernfalls ist es eine unendliche Rekursion, und es tritt Ausnahme für Stapelüberlauf auf.

Also solltest du design die Rekursionsfunktion so gestalten. Ein Beispiel binäre Suche in einem sortierten Array :

BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = low + ((high - low) / 2)  // Note: not (low + high) / 2 !!
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
}
1
Emre

Die beste Möglichkeit, eine rekursive Schleife zu verlassen, wenn ein Fehler auftritt, ist das Auslösen einer Laufzeitausnahme.

throw new RuntimeException("Help!  Somebody debug me!  I'm crashing!");

Natürlich tötet dies Ihr Programm, aber Sie sollten die Bereichsüberprüfung und Algorithmusanalyse verwenden, um sicherzustellen, dass Ihre Rekursion keine solche Ausnahme auslöst. Möglicherweise möchten Sie einen rekursiven Algorithmus durchbrechen, weil Ihnen der Speicher knapp wird. Hier können Sie ermitteln, wie viel Speicher Ihr Algorithmus auf dem Stack benötigt. Wenn Sie beispielsweise Java codieren, vergleichen Sie diese Berechnung mit

getMemoryInfo.availMem().

Angenommen, Sie verwenden Rekursion, um n! Zu finden. Ihre Funktion sieht ungefähr so ​​aus:

public long fact(int n)
{
    long val = 1;
    for (int i  = 1, i<=n,i++)
        return val *= fact(i);
    return val;
}

Überprüfen Sie vor dem Ausführen, dass Sie (n Anzahl Bytes in einem langen, 8 in Java) * n Bytes im Speicher haben, um den gesamten Stack aufzunehmen. Grundsätzlich sollten Sie mit der Bereichs- und Fehlerprüfung vor der rekursiven Methode/Funktion nicht ausbrechen. Abhängig von Ihrem Algorithmus müssen Sie jedoch möglicherweise dem gesamten Stack signalisieren, dass Sie bereit sind zu gehen. Wenn das der Fall ist, funktioniert Toms Antwort.

0
samdoj

Wenn nicht rekursive Aufrufe parallel ausgewertet werden, müssen Sie wahrscheinlich nur eine Logik hinzufügen, um den Wert des ersten rekursiven Aufrufs zu prüfen, bevor Sie den zweiten rekursiven Aufruf (und den nachfolgenden, wenn nicht eine binäre Baumstruktur) aufrufen.

public abstract class Tree {

    protected abstract boolean headIsViolation();

    protected abstract boolean isLeaf();

    public Tree getLeft();

    public Tree getRight();

    // Recursive
    public boolean checkViolation() {
        if(this.isLeaf()) {
            return this.headIsViolation();
        }

        // If needed, you could pass some sort of 'calculation state'
        // object through the recursive calls and evaluate the violation
        // through that object if the current node is insufficient
        if(this.headIsViolation()) {
            // Terminate the recursion
            return true;
        }

        // Fortunately, Java short-circuits ||
        // So if the left child is in violation, the right child will
        // not even be checked
        return this.getLeft().checkViolation() || this.getRight().checkViolation();
    }
}
0
Greg Case

Vielleicht möchten Sie eine Rekursion vermeiden und durch einen Stapel ersetzen. Auf diese Weise können Sie die Operation unterbrechen, während Sie etwas tun können, das einer rekursiven Operation ähnelt. Tatsächlich simulieren Sie die Rekursion nur selbst.

Ich habe hier eine nette Erklärung gefunden: http://haacked.com/archive/2007/03/04/Replacing_Recursion_With_a_Stack.aspx/

0
murphy

Ich konnte aus allen rekursiven Aufrufen mit einer globalen Variablen aussteigen.

boolean skipRecursivePaths = false;
private callAgain(){

if(callAgain){
  if(getOutCompletely){

    skipRecursivePaths = true;
    }
    if(skipRecursivePaths){
    return;
    }
}
0
roho