Scala for Backend Engineering & Functional Programming · Lektion

Akkumulator-Muster

In eine endrekursive Funktion umwandeln

Akkumulator-Muster ist eine kostenlose Scala for Backend Engineering & Functional Programming-Lektion auf CoddyKit. Dies ist Lektion 3 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.

Das Akkumulatormuster

Das Akkumulatormuster wandelt eine nicht endrekursive Funktion in eine endrekursive um. Sie führen das Teilergebnis in einem zusätzlichen Parameter, dem Akkumulator, mit, statt es nach der Rückkehr des Aufrufs aufzubauen.

Die Grundidee

Statt n + sum(n-1) zu verwenden, wobei die Arbeit nach dem Aufruf erfolgt, berechnen Sie die neue Teilsumme vor dem Aufruf: sum(n-1, acc + n). Nun ist der rekursive Aufruf die letzte Aktion.

Vorher: nicht endrekursive Summe

Diese direkte Version ist nicht endrekursiv: Die Addition wartet auf den rekursiven Aufruf.

object Main {
  def sum(n: Int): Int =
    if (n == 0) 0 else n + sum(n - 1)

  def main(args: Array[String]): Unit = {
    println(sum(50))
  }
}

Nachher: Endrekursive Summe mit Akkumulator

Fügen Sie einen Parameter acc hinzu, der die laufende Summe enthält. Der rekursive Aufruf befindet sich nun in Endposition und kann optimiert werden.

import scala.annotation.tailrec

object Main {
  @tailrec
  def sum(n: Int, acc: Int = 0): Int =
    if (n == 0) acc else sum(n - 1, acc + n)

  def main(args: Array[String]): Unit = {
    println(sum(50))
  }
}

Endrekursive Fakultät

Wenden Sie dieselbe Umwandlung auf die Fakultät an: Multiplizieren Sie den Wert vor dem rekursiven Aufruf in den Akkumulator.

import scala.annotation.tailrec

object Main {
  @tailrec
  def factorial(n: Int, acc: Long = 1): Long =
    if (n <= 1) acc else factorial(n - 1, acc * n)

  def main(args: Array[String]): Unit = {
    println(factorial(10))
  }
}

Den Akkumulator verbergen

Der zusätzliche Parameter ist ein Implementierungsdetail. Umschließen Sie die endrekursive Arbeitsfunktion mit einer übersichtlichen öffentlichen Funktion, damit Aufrufer acc nicht sehen.

import scala.annotation.tailrec

object Main {
  def factorial(n: Int): Long = {
    @tailrec
    def loop(m: Int, acc: Long): Long =
      if (m <= 1) acc else loop(m - 1, acc * m)
    loop(n, 1)
  }

  def main(args: Array[String]): Unit = {
    println(factorial(6))
  }
}

Eine Liste akkumulieren

Mit diesem Muster lassen sich auch Collections aufbauen. Eine endrekursive Umkehrfunktion stellt jeden Kopf der Akkumulatorliste voran.

import scala.annotation.tailrec

object Main {
  def reverse[A](xs: List[A]): List[A] = {
    @tailrec
    def loop(rem: List[A], acc: List[A]): List[A] = rem match {
      case Nil    => acc
      case h :: t => loop(t, h :: acc)
    }
    loop(xs, Nil)
  }

  def main(args: Array[String]): Unit = {
    println(reverse(List(1, 2, 3, 4)))
  }
}

Reihenfolge der Akkumulation

Beachten Sie, dass das Voranstellen beim Akkumulator die Reihenfolge auf natürliche Weise umkehrt. Bei einer Funktion zum Erstellen von Listen, die die Reihenfolge beibehält, bauen Sie die Liste häufig umgekehrt auf und kehren sie am Ende um oder verwenden eine effiziente Struktur zum Anhängen.

Endrekursives map

Bauen Sie mit einem Akkumulator eine Ergebnisliste auf und kehren Sie sie anschließend einmal um, um die ursprüngliche Reihenfolge wiederherzustellen.

import scala.annotation.tailrec

object Main {
  def mapTail[A, B](xs: List[A])(f: A => B): List[B] = {
    @tailrec
    def loop(rem: List[A], acc: List[B]): List[B] = rem match {
      case Nil    => acc.reverse
      case h :: t => loop(t, f(h) :: acc)
    }
    loop(xs, Nil)
  }

  def main(args: Array[String]): Unit = {
    println(mapTail(List(1, 2, 3))(_ * 10))
  }
}

Beziehung zu foldLeft

Das Akkumulatormuster entspricht genau dem, was foldLeft verallgemeinert: Es führt einen Akkumulator rekursiv durch das Ende einer Collection. Viele manuelle Akkumulatorfunktionen lassen sich als einzelnes foldLeft neu schreiben.

@main def run(): Unit = {
  val total = List(1, 2, 3, 4).foldLeft(0)(_ + _)
  println(total)
}

Wann Sie es verwenden sollten

Verwenden Sie das Akkumulatormuster, wenn eine rekursive Funktion eine große lineare Struktur verarbeitet und andernfalls einen Stack-Overflow verursachen würde. Es tauscht eine etwas weniger offensichtliche Struktur gegen garantierte Stapelsicherheit.

Kurztest

Testen Sie Ihr Verständnis des Akkumulatormusters.

Zusammenfassung

Sie haben das Akkumulatormuster kennengelernt:

Führen Sie das Teilergebnis in einem zusätzlichen Parameter mit.
Berechnen Sie es vor dem rekursiven Aufruf, um die Endposition zu erreichen.
Verbergen Sie den Akkumulator hinter einer übersichtlichen öffentlichen Funktion.
Das Muster wird durch foldLeft verallgemeinert.

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“?

In eine endrekursive Funktion umwandeln 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 3 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

← Zurück zu Scala for Backend Engineering & Functional Programming