Wie man in einem rekursiven Algorithmus in Java die Dinge erledigt hält?

Question

Ich habe einen rekursiven Algorithmus, der Zeichen für Zeichen durchläuft und analysiert, um eine baumartige Struktur zu erzeugen. Ich möchte in der Lage sein, den Zeichenindex zu verfolgen, in dem sich der Parser befindet (für Fehlermeldungen genauso wie alles andere), bin aber nicht scharf darauf, etwas wie ein Tupel zu implementieren, um mehrere zurückgegebene Typen zu behandeln.

Ich versuchte mit einem Integer-Typ, außerhalb der Methode deklariert und in die rekursive Methode übergeben, aber weil es endgültig ist, sind rekursive Aufruf Inkremente "vergessen", wenn ich zurückkomme. (Weil das Inkrement des Integer-Werts den Wert des übergebenen Objektreferenzpunkts an einem neuen Objekt festlegt)

Gibt es eine Möglichkeit, etwas ähnliches zur Arbeit zu bekommen, das meinen Code nicht verschmutzt?

Answer 1

Da Sie bereits die pseudo-wandelbar integer „Hack“, entdeckt, wie zu dieser Option:

Ist es sinnvoll für Sie eine separate Klasse Parser zu machen? Wenn Sie dies tun, können Sie den aktuellen Status in einer Mitgliedsvariablen speichern. Sie müssen wahrscheinlich darüber nachdenken, wie Sie mit Thread-Sicherheitsproblemen umgehen, und es könnte für diese spezielle Anwendung übertrieben sein, aber es könnte für Sie arbeiten.

Answer 2

Es ist ein bisschen ein Hack, aber manchmal verwende ich einen AtomicInteger, der veränderbar ist, um solche Dinge zu tun. Ich habe auch Fälle, in denen ein int [] der Größe 1 in geben wird

Answer 3

Die aktuelle Lösung Ich verwende ist.

int[] counter = {0}; 

und es dann an den rekursiven Algorithmus übergeben:

public List<Thing> doIt (String aString, int[] counter) { ... } 

und wenn ich will es erhöhen:

counter[0]++; 

nicht super elegant, aber es funktioniert ...

Answer 4

Ganzzahlen sind unveränderlich, dh wenn Sie sie als Argument übergeben, erstellt sie eine Kopie und nicht eine Referenz auf dasselbe Element. (explanation).

Um das gewünschte Verhalten zu erhalten, können Sie Ihre eigene Klasse schreiben, die wie Integer nur änderbar ist. Übergeben Sie es dann einfach an die rekursive Funktion, es wird innerhalb der Rekursion inkrementiert, und wenn Sie nach dem Ende der Rekursion wieder darauf zugreifen, behält es seine neuen Werte bei.

Bearbeiten: Beachten Sie, dass die Verwendung eines int [] -Arrays eine Variation dieser Methode ist ... In Java werden Arrays auch durch Verweis übergeben und nicht wie primitive oder unveränderliche Klassen kopiert.

Answer 5

Um ehrlich zu sein würde ich die Funktion umwandeln, um es zu einem linearen Algorithmus zu machen, der eine Schleife verwendet. Auf diese Weise haben Sie keine Chance, den Heapspeicherplatz zu verlieren, wenn Sie eine extrem große Zeichenfolge durchlaufen. Außerdem brauchen Sie keinen zusätzlichen Parameter, um die Anzahl zu überwachen.

Dies würde wahrscheinlich auch dazu führen, dass der Algorithmus schneller wird, da kein Funktionsaufruf für jedes Zeichen erforderlich ist.

Es sei denn, es gibt einen bestimmten Grund, dass es rekursiv sein muss.

Answer 6

Eine Möglichkeit, die ich mir vorstellen kann, besteht darin, die Anzahl in einer Mitgliedsvariablen der Klasse zu speichern.Dies setzt natürlich voraus, dass die öffentliche doIt Methode nur von einem einzigen Thread aufgerufen wird.

Eine andere Möglichkeit besteht darin, die öffentliche Methode so umzuformulieren, dass sie eine private Hilfsmethode aufruft. Die private Methode übernimmt die Liste als Parameter und gibt die Anzahl zurück. Zum Beispiel:

public List<Thing> doIt(String aString) { 
    List<Thing> list = new ArrayList<Thing>(); 
    int count = doItHelper(aString, list, 0); 
    // ... 
    return list; 
} 

private int doItHelper(String aString, List<Thing> list, int count) { 
    // ... 
    // do something that updates count 
    count = doItHelper(aString, list, count); 
    // ... 
    return count; 
} 

Dies setzt voraus, dass Sie den Fehler machen können in der Öffentlichkeit doIt Methode Handhabung, da die count Variable tatsächlich nicht zurück an den Aufrufer übergeben. Wenn Sie das tun müssen, könnten Sie natürlich eine Ausnahme auslösen:

public List<Thing> doIt(String aString) throws SomeCustomException { 
    List<Thing> list = new ArrayList<Thing>(); 
    int count = doItHelper(aString, list, 0); 
    // ... 
    if (someErrorOccurred) { 
     throw new SomeCustomException("Error occurred at chracter index " + count, count); 
    } 
    return list; 
} 

Es ist schwierig zu wissen, ob das mehr ohne zu wissen, helfen, wie Ihr Algorithmus tatsächlich funktioniert.

Answer 7

Sie könnten einfach eine statische int-Klassenvariable verwenden, die bei jedem Aufruf Ihrer doIt-Methode inkrementiert wird.

Answer 8

Sie könnten auch tun:

private int recurse (int i) { 

    if (someConditionkeepOnGoing) { 
     i = recurse(i+1); 
    } 

    return i; 
}