Lassen Sie uns ein einfaches Programm schreiben, um Zahlen von n bis 0 zu addieren. Aber warum versuchen Sie es nicht mit einem rekursiven Ansatz, anstatt einen iterativen Ansatz zu verwenden?

Wir nennen dieses Programm sum. Wir wissen sum(0) == 0, also ist dies unser Basisszenario. Wie kommen wir zum Basisfall? sum(n) == n sum(n-1), bis wir endlich sum(0) erreichen. Der Java-Code lautet wie folgt:

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

Rekursionsproblem?

Rekursion weist einen inh?renten Fehler auf, wenn der Basisfall weit vom Eingabewert entfernt ist ... In den meisten Sprachen verwenden Funktionsaufrufe den Stapel des Programms, um Funktionsaufrufinformationen zu speichern, sodass sehr gro?e Rekursionen einen Stapelüberlauf verursachen k?nnen.

Aber gibt es eine M?glichkeit, dies zu vermeiden? Tats?chlich gibt es das. Dies ist eine alte Strategie namens Trampolin.

Sprungbrett

Die Grundidee der Springboard-Strategie besteht darin, dass ein Teil des Programms einen ?Wert“ oder eine ?Fortsetzung“ zurückgibt. Was ist Fortsetzung? Eine Funktion, die die Verarbeitung fortsetzt.

Es ist ungef?hr so:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

sum?

Lassen Sie uns sum das Programm wie folgt modellieren: Anstatt einfach zu rekursieren, verwenden Sie Fortsetzungen. Eine M?glichkeit besteht darin, acc als Objekt zu verwenden, das über eine Fortsetzung übergeben wird. Wenn also sum_trampoline(0, acc) erreicht ist, kehren wir zu acc zurück. Wie geht es weiter?

Gehen wir von sum_trampoline(n, acc) zu sum_trampoline(n-1, acc n). Die erste Eingabe ist sum_trampoline(n, 0).

Der Code lautet also wie folgt:

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}

Verwenden Sie Typen, um Sprungbretter zu beschreiben

Das Sprungbrett muss ungef?hr die folgende Form haben:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

Aber das gibt viel Codierungsfreiheit und ist für die Java-Welt nicht sehr intuitiv. Wir k?nnen überprüfen, ob es sich um eine Fortsetzung handelt, indem wir das Objekt fragen. Was w?re, wenn wir fragen würden: ?Wurde der Wert gefunden?“ Da Java keine Summentypen hat, gibt return trampolim tats?chlich den Typ trampolim zurück, anstatt den Wert zurückzugeben. Wir k?nnen zu trampolim.value() zurückkehren.

Ein wichtiger Punkt ist schlie?lich das Bootstrapping des Sprungbretts. Dazu k?nnen wir eine Funktion verwenden, um die Eingabe in den entsprechenden Pogo-Rückgabewert umzuwandeln. Eingaben und Ergebnisse k?nnen zur besseren Nutzung verallgemeinert werden:

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}

TrampolineStep<R>Was ist mit der Schnittstelle?

Es definiert drei Methoden:

• gotValue: Fragt, ob der Wert gefunden wurde
• value: Gibt den gefundenen Wert
zurück
• runNextStep: Gibt einen Wert oder eine Fortsetzung zurück

Es gibt grunds?tzlich zwei Zust?nde:

• Wert gefunden
• Es ist eine Fortsetzung

Daher k?nnen wir statische Methoden verwenden, um es zu initialisieren. In F?llen, in denen der Wert gefunden wurde, muss der Wert übergeben werden:

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

Im Falle einer Fortsetzung müssen Sie angeben, wie Sie zum n?chsten Element der Fortsetzung gelangen:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

sum_trampolineWie wird dies erreicht?

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}

Tail Call Fibonacci

Die klassische Implementierung von Fibonacci folgt der rekursiven Definition:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

Es gibt auch eine iterative Version, die die Fibonacci-Definition nicht rekursiv, sondern vorw?rts erweitert: beginnend bei 0 und 1, bis die entsprechenden Werte erreicht sind:

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}

Es gibt eine Vorw?rtsversion dieser Implementierung, die ?Tail Call Recursion“ verwendet:

static <X> TrampolineStep<X> valueFound(X value) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return true;
        }

        @Override
        public X value() {
            return value;
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return this;
        }
    };
}

Hier trenne ich die Eingabeschnittstelle, die die Zahlen vorbereitet, die im rekursiven Fibonacci-Endaufruf verwendet werden. Im weiteren Verlauf beginnen wir mit der Zuordnung fib[0] => 0, fib[1] => 1 und navigieren von Index 0 bis wir Index n erreichen.

Fibonacci: Vom Tail Call zum Sprungbrett

fib_tc veranschaulicht das Fibonacci-Sprungbrett gut:

static <X> TrampolineStep<X> goonStep(Supplier<TrampolineStep<X>> x) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return false;
        }

        @Override
        public X value() {
            throw new RuntimeException("dont call this");
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return x.get();
        }
    };
}

Bitte beachten Sie, dass dies nur ein Grundgerüst ist und eine vollst?ndige Implementierung der TrampolineStep-Schnittstelle und eine vollst?ndige Implementierung der trampoline-Funktionen zum Kompilieren und Ausführen erfordert. Darüber hinaus muss IN durch einen bestimmten Eingabetyp ersetzt werden.

Das obige ist der detaillierte Inhalt vonTrampolin, Beispiel in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!