Sprungbrett zu Funktionen jenseits des rekursiven Primitivs? Implementierung für die Ackermann-Peter-Funktion

Als ich die Sprungbretttechnik erkundete, habe ich sie zunächst in einfacheren Situationen mit nur einer Rekursion verwendet – wahrscheinlich einer richtigen Teilmenge primitiver rekursiver Funktionen. Es ergab sich jedoch die Notwendigkeit, bei der Arbeit eine extrem lange Berechnung durchzuführen. Meine erste Idee war die Funktion Busy Beaver, aber zusätzlich zu ihrer hohen Rechenkomplexität war ich nicht vertraut genug. Ich habe mich dann für eine bekanntere Funktion entschieden: die Ackermann-Peter-Funktion.

Die Ackermann-Peter-Funktion

Dies ist eine leicht verständliche Funktion, die zwei ganzzahlige Argumente als Eingabe verwendet:

int ackermannPeter(int m, int n) {
    if (m == 0) {
        return n + 1;
    } else if (n == 0) {
        return ackermannPeter(m - 1, 1);
    }
    return ackermannPeter(m - 1, ackermannPeter(m, n - 1));
}

Weitere Einzelheiten finden Sie auf der Wikipedia-Seite oder bei WolframAlpha.

Verwenden der Funktion

Beim Test ackermannPeter(3, 3) wurde das Ergebnis korrekt berechnet. Bei der Ausführung von ackermannPeter(4, 3) kam es jedoch zu einer Stapelexplosion. Die Tiefe rekursiver Aufrufe der Ackermann-Peter-Funktion ist sehr groß; Durch einfaches Ändern des ersten Arguments von 3 auf 4 wurde die Ausgabe, die 61 war, zu $2^{2^{65536}} - 3$.

Stapellimit überwinden

Das Problem liegt in der intensiven Rekursion der Ackermann-Peter-Funktion, die den Stapel schnell erschöpft. Die Lösung besteht darin, Fortsetzungen zu verwenden, um eine Überlastung des Stapels zu vermeiden und so die Sprungbrettidee umzusetzen.

Ein Schritt auf dem Trampolin erfordert drei Verhaltensweisen:

• Geben Sie an, ob die Berechnung abgeschlossen ist.
• Gibt den berechneten Wert zurück.
• Führen Sie einen Schritt aus und erhalten Sie die nächste Fortsetzung.

Für unseren Fall (Ganzzahlrückgabe):

interface Continuation {
    boolean finished();
    int value();
    Continuation step();

    static Continuation found(int v) { /* ... */ }
    static Continuation goon(Supplier<Continuation> nextStep) { /* ... */ }
}

Das Trampolin selbst:

static int compute(Continuation c) {
    while (!c.finished()) {
        c = c.step();
    }
    return c.value();
}

Anwenden auf die Ackermann-Peter-Funktion: Die Funktion ist in drei Fälle unterteilt: Basisfall, einfache Rekursion und doppelte Rekursion. Das Sprungbrett sollte das Ergebnis der zweiten Rekursion steuern. Dazu wird das zweite Argument zu einem Continuation. Wenn n bereits abgeschlossen ist, wird der Vorgang normal fortgesetzt; andernfalls wird ein Schritt in der Fortsetzung ausgeführt und ein neuer generiert.

private static Continuation ackermannPeter(int m, Continuation c) {
    if (!c.finished()) {
        return Continuation.goon(() -> {
            final var next = c.step();
            return Continuation.goon(() -> ackermannPeter(m, next));
        });
    }
    int n = c.value();
    if (m == 0) {
        return Continuation.found(n + 1);
    } else if (n == 0) {
        return Continuation.goon(() -> ackermannPeter(m - 1, Continuation.found(1)));
    }
    return Continuation.goon(() ->
        ackermannPeter(m - 1,
            Continuation.goon(() -> ackermannPeter(m, Continuation.found(n - 1)
        )))
    );
}

Memoisierung hinzufügen

Auswendiglernen verbessert die Leistung. Zwei Situationen: 1) das Ergebnis ist bereits im Speicher; 2) Im nächsten Schritt können Sie auf das aktuelle Ergebnis schließen. Die Memoisierung wird angewendet, nachdem die Fortsetzung des zweiten Arguments gelöst wurde. Die Implementierung mit Memoisierung unter Verwendung einer HashMap- und einer long-Taste (Kombination von m und n) wird vorgestellt und zeigt eine deutliche Reduzierung der Anzahl rekursiver Aufrufe. Die endgültige Version entfernt die globale Speicherabhängigkeit und übergibt HashMap als Argument.

Das obige ist der detaillierte Inhalt vonSprungbrett zu Funktionen jenseits des rekursiven Primitivs? Implementierung für die Ackermann-Peter-Funktion. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!