Akkumulator-Muster
Führen Sie Zustand durch die Rekursion.
Akkumulator-Muster ist eine kostenlose Scala for Backend Engineering & Functional Programming-Lektion auf CoddyKit. Dies ist Lektion 2 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.
Warum Akkumulatoren
Bei einfacher Rekursion wird das Ergebnis auf dem Rückweg durch den Call Stack aufgebaut, nachdem der rekursive Aufruf zurückgekehrt ist.
Ein Akkumulator trägt stattdessen ein laufendes Ergebnis in jeden Aufruf hinein, sodass das Ergebnis beim Erreichen des Basisfalls bereits bereitsteht.
Diese kleine Änderung ermöglicht Endrekursion und eine konstante Stack-Nutzung.
Die Hilfsfunktion
Das Akkumulator-Muster verwendet eine innere Hilfsfunktion, die einen zusätzlichen Parameter für das bisherige Ergebnis erhält.
Die äußere Funktion startet sie lediglich mit einem Anfangswert, häufig 0 oder einer leeren Liste.
def sum(xs: List[Int]): Int = {
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}Den Akkumulator ausführen
Hier summiert das vollständige Programm eine Liste mithilfe eines Akkumulators.
Beachten Sie, dass der Basisfall acc direkt und nicht 0 zurückgibt. Die Summe wurde beim Abstieg durch die Liste aufgebaut.
def sum(xs: List[Int]): Int = {
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}
@main def run(): Unit =
println(sum(List(1, 2, 3, 4))) // 10Die beiden Strukturen vergleichen
Bei einfacher Rekursion wartet der Kombinationsschritt (h + ...) auf den inneren Aufruf.
Bei der Akkumulatorvariante erfolgt die Kombination vor dem Aufruf, und der Aufruf ist das allerletzte, was die Funktion ausführt.
Diese Eigenschaft des letzten Aufrufs macht die Funktion endrekursiv.
// Plain: combine after the call
case h :: t => h + sum(t)
// Accumulator: combine before the call
case h :: t => loop(t, acc + h)Endrekursion
Ein endrekursiver Aufruf liegt vor, wenn der rekursive Aufruf die letzte Aktion der Funktion ist und danach nichts mehr ausgeführt werden muss.
Scala kann dies in eine Schleife optimieren und dabei einen einzigen Stack-Frame wiederverwenden, sodass der Stack unabhängig von der Rekursionstiefe nicht überläuft.
import scala.annotation.tailrec
@tailrec
def countDown(n: Int): Unit =
if (n < 0) ()
else { println(n); countDown(n - 1) }Die Annotation @tailrec
Mit @tailrec weisen Sie den Compiler an zu überprüfen, ob die Funktion tatsächlich endrekursiv ist.
Ist dies nicht der Fall, schlägt die Kompilierung mit einer eindeutigen Fehlermeldung fehl. So wird aus einer unbemerkten Performance-Falle eine Garantie bereits zur Build-Zeit.
import scala.annotation.tailrec
def sum(xs: List[Int]): Int = {
@tailrec
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}
@main def run(): Unit = println(sum((1 to 100000).toList))Eine Liste akkumulieren
Akkumulatoren müssen keine Zahlen enthalten. Sie können auch Collections aufbauen.
Diese reverse-Funktion stellt jeden Kopf dem Akkumulator voran und kehrt dadurch auf natürliche Weise die Reihenfolge um. Das Voranstellen mit :: ist schnell, daher ist diese Lösung effizient.
def reverse[A](xs: List[A]): List[A] = {
def loop(rest: List[A], acc: List[A]): List[A] = rest match {
case Nil => acc
case h :: t => loop(t, h :: acc)
}
loop(xs, Nil)
}Reverse in Aktion
Der Akkumulator beginnt leer und wächst, während die Eingabe verarbeitet wird.
Da jeder Kopf vorne an acc angefügt wird, landet das erste Element am Ende. So entsteht eine umgekehrte Liste bei konstantem Stack-Verbrauch.
def reverse[A](xs: List[A]): List[A] = {
def loop(rest: List[A], acc: List[A]): List[A] = rest match {
case Nil => acc
case h :: t => loop(t, h :: acc)
}
loop(xs, Nil)
}
@main def run(): Unit =
println(reverse(List(1, 2, 3))) // List(3, 2, 1)Mehrere Akkumulatoren
Eine Hilfsfunktion kann mehrere Akkumulatoren gleichzeitig führen.
Hier verfolgen wir in derselben Schleife ein laufendes Produkt und eine Anzahl und geben beide als Tupel zurück.
Jeder Akkumulator übergibt seinen aktualisierten Wert an den nächsten Aufruf.
def stats(xs: List[Int]): (Int, Int) = {
def loop(rest: List[Int], prod: Int, count: Int): (Int, Int) =
rest match {
case Nil => (prod, count)
case h :: t => loop(t, prod * h, count + 1)
}
loop(xs, 1, 0)
}Den Anfangswert auswählen
Der Startwert des Akkumulators muss das neutrale Element Ihrer Operation sein.
Für Addition verwenden Sie 0, für Multiplikation 1, für den Aufbau einer Liste Nil und für das Zusammenfügen von Zeichenketten die leere Zeichenkette.
Ein falscher Startwert führt unbemerkt zu falschen Ergebnissen.
// addition -> seed 0
// product -> seed 1
// list -> seed Nil
// string -> seed ""Reihenfolge der Ergebnisse
Die Akkumulatorrekursion verarbeitet Elemente von links nach rechts, aber ein Akkumulator, der Elemente voranstellt, kehrt ihre Reihenfolge um.
Wenn Sie die Reihenfolge beim Aufbau einer Liste erhalten möchten, können Sie entweder am Ende reverse verwenden oder Elemente anhängen, wobei das Anhängen langsamer ist. Voranstellen und anschließendes Umkehren ist das übliche Idiom.
def mapInc(xs: List[Int]): List[Int] = {
def loop(rest: List[Int], acc: List[Int]): List[Int] = rest match {
case Nil => acc.reverse
case h :: t => loop(t, (h + 1) :: acc)
}
loop(xs, Nil)
}Schnelltest
Wählen Sie die zutreffende Aussage zur Akkumulatorrekursion.
Zusammenfassung
Ein Akkumulator führt das laufende Ergebnis durch die rekursiven Aufrufe, sodass der Basisfall es direkt zurückgeben kann.
Dadurch steht der rekursive Aufruf an der Endposition. Das ermöglicht die Tail-Call-Optimierung von Scala und die Sicherheitsprüfung durch @tailrec.
Initialisieren Sie den Akkumulator mit dem neutralen Element der Operation und kehren Sie die Liste am Ende um, wenn die Reihenfolge wichtig ist.
Häufig gestellte Fragen
Ist die Lektion „Akkumulator-Muster“ kostenlos?
Ja — der vollständige Text von „Akkumulator-Muster“ 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 „Akkumulator-Muster“?
Führen Sie Zustand durch die 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 2 von 4.
Wie lange dauert die Lektion „Akkumulator-Muster“?
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.
Alle Lektionen in diesem Kurs
- Rekursiv denken
- Akkumulator-Muster
- foldLeft und foldRight
- reduce und aggregate