Wie kann man in einem rekursiven Algorithmus in Java die Anzahl der „erledigten Dinge“ aufrechterhalten?

Question

Ich habe einen rekursiven Algorithmus, der eine Zeichenfolge Zeichen für Zeichen durchgeht und sie analysiert, um eine baumartige Struktur zu erstellen.Ich möchte in der Lage sein, den Zeichenindex zu verfolgen, an dem sich der Parser gerade befindet (sowohl für Fehlermeldungen als auch für alles andere), bin aber nicht daran interessiert, so etwas wie ein Tupel zu implementieren, um mehrere zurückgegebene Typen zu verarbeiten.

Ich habe versucht, einen Integer-Typ zu verwenden, der außerhalb der Methode deklariert und an die rekursive Methode übergeben wurde, aber da es sich um einen endgültigen Typ handelt, werden rekursive Aufrufinkremente bei meiner Rückkehr „vergessen“.(Da die Erhöhung des Integer-Werts dazu führt, dass der als Wert übergebene Objektreferenzpunkt auf ein neues Objekt verweist)

Gibt es eine Möglichkeit, etwas Ähnliches zum Laufen zu bringen, das meinen Code nicht verschmutzt?

Answer 1

Da Sie den pseudoveränderlichen Integer-„Hack“ bereits entdeckt haben, wie wäre es mit dieser Option:

Ist es für Sie sinnvoll, eine separate Parser-Klasse zu erstellen?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. Für diese spezielle Anwendung ist das möglicherweise übertrieben, für Sie funktioniert es jedoch möglicherweise.

Answer 2

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

Answer 3

Die aktuelle Lösung, die ich verwende, ist:

int[] counter = {0};

und übergeben Sie es dann an den rekursiven Algorithmus:

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

und wenn ich es erhöhen möchte:

counter[0]++;

Nicht besonders elegant, aber es funktioniert...

Answer 4

Ganzzahlen sind unveränderlich, was bedeutet, dass bei der Übergabe als Argument eine Kopie und kein Verweis auf dasselbe Element erstellt wird.(Erläuterung).

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

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

Answer 5

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

Answer 6

Sie könnten auch Folgendes tun:

private int recurse (int i) {

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

    return i;
}

Answer 7

Ehrlich gesagt würde ich die Funktion umkodieren, um sie zu einem linearen Algorithmus zu machen, der eine Schleife verwendet.Auf diese Weise besteht keine Gefahr, dass Ihnen der Heap-Speicherplatz ausgeht, wenn Sie einen extrem großen String durchlaufen.Außerdem benötigen Sie keinen zusätzlichen Parameter, nur um die Anzahl zu verfolgen.

Dies würde wahrscheinlich auch dazu führen, dass der Algorithmus schneller wird, da nicht für jedes Zeichen ein Funktionsaufruf durchgeführt werden muss.

Es sei denn natürlich, es gibt einen bestimmten Grund, warum es rekursiv sein muss.

Answer 8

Eine Möglichkeit, die mir einfällt, besteht darin, die Anzahl in einer Mitgliedsvariablen der Klasse zu speichern.Dies setzt natürlich voraus, dass die Öffentlichkeit doIt Methode wird nur von einem einzelnen Thread aufgerufen.

Eine andere Möglichkeit besteht darin, die öffentliche Methode umzugestalten, um eine private Hilfsmethode aufzurufen.Die private Methode verwendet 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 die Fehlerbehandlung öffentlich durchführen können doIt Methode, da die count Variable wird nicht wirklich an den Aufrufer zurückgegeben.Wenn Sie das tun müssen, können 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 schwer zu sagen, ob das hilft, ohne mehr darüber zu wissen, wie Ihr Algorithmus tatsächlich funktioniert.