Trampolining
Stack-sichere Rekursion
Trampolining ist eine kostenlose Scala for Backend Engineering & Functional Programming-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Scala for Backend Engineering & Functional Programming-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Scala for Backend Engineering & Functional Programming-Kurs umfasst insgesamt 4 Lektionen.
Die Grenze von @tailrec
@tailrec optimiert nur eine Funktion, die sich direkt selbst aufruft. Bei gegenseitiger Rekursion (zwei Funktionen, die sich gegenseitig aufrufen) hilft die Annotation nicht; der Stapel wächst weiterhin. Trampolining löst dieses Problem.
Das Problem der gegenseitigen Rekursion
Betrachten Sie isEven und isOdd, die jeweils mithilfe der anderen Funktion definiert sind. Bei einer großen Zahl führt dies zu einem Stack-Overflow, und keine der beiden Funktionen kann mit @tailrec annotiert werden.
object Main {
def isEven(n: Int): Boolean = if (n == 0) true else isOdd(n - 1)
def isOdd(n: Int): Boolean = if (n == 0) false else isEven(n - 1)
def main(args: Array[String]): Unit = {
println(isEven(10))
}
}Was ist ein Trampolin?
Ein Trampolin wandelt rekursive Aufrufe in Daten um. Statt sich selbst aufzurufen, gibt eine Funktion eine Beschreibung des nächsten Schritts zurück. Eine Treiberschleife führt diese Schritte wiederholt aus und hält den Stapel flach.
TailRec in der Standardbibliothek
Scala stellt scala.util.control.TailCalls mit dem Typ TailRec bereit. Verwenden Sie done(x) für ein endgültiges Ergebnis und tailcall(...), um den nächsten Aufruf zurückzustellen.
import scala.util.control.TailCalls._
object Main {
def isEven(n: Int): TailRec[Boolean] =
if (n == 0) done(true) else tailcall(isOdd(n - 1))
def isOdd(n: Int): TailRec[Boolean] =
if (n == 0) done(false) else tailcall(isEven(n - 1))
def main(args: Array[String]): Unit = {
println(isEven(100000).result)
}
}done und tailcall
Die beiden grundlegenden Bausteine:
done(value)verpackt ein endgültiges Ergebnis.tailcall(expr)stellt einen Aufruf zurück, der einTailRecliefert.
Der Aufruf von .result führt die Trampolinschleife aus und erzeugt den Wert.
Stapelsicherheit
Da jeder tailcall die Kontrolle an die Treiberschleife zurückgibt, statt einen verschachtelten Java-Aufruf zu erzeugen, wächst der JVM-Stapel nicht mit der Rekursionstiefe. Das obige Beispiel verarbeitet 100.000 Schritte ohne Überlauf.
Selbstrekursion per Trampolining
Trampolines funktionieren auch bei gewöhnlicher tiefer Selbstrekursion, wenn sich ein Akkumulator nicht einfach verwenden lässt. Hier bleibt ein tiefer Countdown stapelsicher.
import scala.util.control.TailCalls._
object Main {
def countDown(n: Int): TailRec[Int] =
if (n == 0) done(0) else tailcall(countDown(n - 1))
def main(args: Array[String]): Unit = {
println(countDown(500000).result)
}
}Ergebnisse mit flatMap kombinieren
TailRec unterstützt map und flatMap. Dadurch können Sie nach einem zurückgestellten Aufruf Arbeit ausführen und bleiben dennoch stapelsicher.
import scala.util.control.TailCalls._
object Main {
def sum(n: Int): TailRec[Int] =
if (n == 0) done(0)
else tailcall(sum(n - 1)).map(_ + n)
def main(args: Array[String]): Unit = {
println(sum(100000).result)
}
}Funktionsweise der Treiberschleife
Konzeptionell führt .result eine Schleife aus: Sie nimmt den aktuellen Schritt; handelt es sich um done, gibt sie dessen Wert zurück; handelt es sich um einen zurückgestellten Aufruf, wertet sie eine Ebene aus und fährt fort. Das Ganze benötigt konstanten Stapelplatz.
Trampolining in Effect-Bibliotheken
Bibliotheken wie Cats Effect und ZIO verwenden intern Trampolining für ihre flatMap-Ketten. Deshalb können Sie tief verschachtelte Effect-Programme erstellen, ohne einen Stack-Overflow zu verursachen. Trampolining bildet die Grundlage stapelsicherer funktionaler Effects.
Wann Sie Trampolining verwenden sollten
Verwenden Sie einen Trampolin, wenn:
- Sie gegenseitige Rekursion haben, die sich nicht als eine einzige endrekursive Funktion formulieren lässt.
- Die Rekursion zu tief für den Stack ist und ein Akkumulator nicht infrage kommt.
Bei einfacher Selbstrekursion sollten Sie zuerst @tailrec mit einem Akkumulator bevorzugen.
Kurzer Test
Testen Sie Ihr Verständnis von Trampolining.
Zusammenfassung
Sie haben Trampolining gelernt:
- Es macht gegenseitige und sehr tiefe Rekursion stack-sicher.
- Verwenden Sie
TailCalls:done(x)undtailcall(...), anschließend.result. TailRecunterstütztmap/flatMap.- Es bildet die Grundlage stack-sicherer Effektbibliotheken.
Häufig gestellte Fragen
Ist die Lektion „Trampolining“ kostenlos?
Ja — der vollständige Text von „Trampolining“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Scala for Backend Engineering & Functional Programming-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Scala for Backend Engineering & Functional Programming-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Trampolining“?
Stack-sichere Rekursion Du übst Scala for Backend Engineering & Functional Programming mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Scala for Backend Engineering & Functional Programming zu starten?
Keine Vorkenntnisse erforderlich. Scala for Backend Engineering & Functional Programming auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Trampolining“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Scala for Backend Engineering & Functional Programming-Lektion Code schreiben und ausführen?
Ja. Jede Scala for Backend Engineering & Functional Programming-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.