Scala for Backend Engineering & Functional Programming · Lektion

Rekursiv denken

Abbruchfälle und rekursive Schritte.

Rekursiv denken ist eine kostenlose Scala for Backend Engineering & Functional Programming-Lektion auf CoddyKit. Dies ist Lektion 1 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.

Was Rekursion bedeutet

Rekursion bedeutet, dass eine Funktion sich selbst aufruft, um eine kleinere Variante desselben Problems zu lösen.

In Scala eignet sich Rekursion besonders gut für die funktionale Programmierung, weil sich damit Schleifen ohne veränderliche Variablen ausdrücken lassen.

Jede rekursive Funktion benötigt zwei Dinge: eine Möglichkeit zum Beenden und eine Möglichkeit, das Problem zu verkleinern.

Zuerst der Basisfall

Der Basisfall ist die einfachste Eingabe, die die Funktion direkt und ohne weitere Rekursion beantworten kann.

Ohne Basisfall würde die Funktion sich endlos selbst aufrufen und mit einem StackOverflowError abstürzen.

Entwerfen Sie den Basisfall immer vor dem rekursiven Schritt.

def countdown(n: Int): Unit =
  if (n < 0) ()           // base case: stop
  else {
    println(n)
    countdown(n - 1)      // recursive step
  }

Eine erste rekursive Funktion

Hier sehen Sie ein vollständiges Programm, das die Zahlen von 1 bis n summiert.

Der Basisfall gibt 0 zurück; der rekursive Fall addiert n zur Summe aller darunterliegenden Zahlen.

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

@main def run(): Unit =
  println(sum(5))   // 15

Aufrufe nachvollziehen

Um Rekursion zu verstehen, führen Sie die Aufrufe von Hand auseinander.

sum(3) wird zu 3 + sum(2), daraus wird 3 + 2 + sum(1), und schließlich 3 + 2 + 1 + sum(0).

Erst wenn sum(0) den Wert 0 zurückgibt, löst sich die Kette wieder zu einem einzelnen Wert auf: 6.

// sum(3)
// = 3 + sum(2)
// = 3 + (2 + sum(1))
// = 3 + (2 + (1 + sum(0)))
// = 3 + (2 + (1 + 0))
// = 6

Rekursion mit Listen

Listen sind von Natur aus rekursiv: Eine Liste ist entweder leer (Nil) oder besteht aus einem Kopf und einem kleineren Rest.

Diese Struktur lässt sich direkt auf rekursive Funktionen übertragen. Die leere Liste ist der Basisfall; der Kopf zusammen mit der Rekursion auf dem Rest bildet den rekursiven Schritt.

def length[A](xs: List[A]): Int = xs match {
  case Nil     => 0
  case _ :: t  => 1 + length(t)
}

Den Rest per Pattern Matching zerlegen

Das ::-Muster teilt eine nicht leere Liste in ihren Kopf und ihren Rest auf.

Jeder rekursive Aufruf arbeitet mit einer strikt kürzeren Liste und bewegt sich dadurch garantiert auf Nil zu.

Dies ist die übliche Vorgehensweise, um eine Liste in Scala rekursiv zu durchlaufen.

def sumList(xs: List[Int]): Int = xs match {
  case Nil    => 0
  case h :: t => h + sumList(t)
}

@main def run(): Unit =
  println(sumList(List(1, 2, 3, 4)))  // 10

Zwei rekursive Aufrufe

Manche Probleme verzweigen sich in mehr als einen rekursiven Aufruf.

Das klassische Beispiel ist Fibonacci, bei dem jeder Wert von den beiden vorherigen Werten abhängt.

Diese naive Variante ist einfach, aber langsam, weil sie dieselben Werte sehr oft neu berechnet.

def fib(n: Int): Int =
  if (n < 2) n
  else fib(n - 1) + fib(n - 2)

@main def run(): Unit =
  println(fib(7))   // 13

Die Kosten für den Stack

Jeder rekursive Aufruf fügt dem Call Stack einen Stack-Frame hinzu, der auf die Rückkehr des inneren Aufrufs warten muss.

Bei sehr tiefer Rekursion kann der Stack erschöpft werden und einen StackOverflowError auslösen.

Wenn Sie die Rekursionstiefe und nicht nur die Datengröße betrachten, können Sie dieses Risiko besser einschätzen.

// This would overflow the stack for large n:
// def deep(n: Int): Int =
//   if (n == 0) 0 else 1 + deep(n - 1)
// deep(1000000)  // StackOverflowError

Auf den Basisfall zulaufen

Die entscheidende Invariante der Rekursion lautet: Jeder Aufruf muss sich dem Basisfall nähern.

Wenn das Argument nicht kleiner wird oder die Abbruchbedingung nie erreicht, endet die Rekursion nicht.

Prüfen Sie dies, bevor Sie etwas ausführen.

def reverse[A](xs: List[A]): List[A] = xs match {
  case Nil    => Nil
  case h :: t => reverse(t) :+ h   // t is smaller than xs
}

Rekursion und Schleifen

Imperativer Code verwendet while-Schleifen mit veränderlichen Zählern; funktionaler Code verwendet Rekursion mit unveränderlichen Werten.

Beide Ansätze können dieselben Berechnungen ausdrücken, aber Rekursion beschreibt die Struktur der Daten unmittelbarer.

In Scala bevorzugen Sie häufig Rekursion oder Funktionen höherer Ordnung gegenüber einfachen Schleifen.

// Imperative
var total = 0
for (i <- 1 to 5) total += i

// Recursive
def sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1)

Eine rekursive Lösung entwerfen

Ein zuverlässiges Vorgehen: Identifizieren Sie den Basisfall, nehmen Sie an, dass der rekursive Aufruf für die kleinere Eingabe bereits funktioniert, und kombinieren Sie dann den Kopf mit diesem Ergebnis.

Dieser Vertrauensvorschuss ist der Kern des rekursiven Denkens. Sie verlassen sich auf den kleineren Aufruf und behandeln nur einen Schritt.

def maxOf(xs: List[Int]): Int = xs match {
  case h :: Nil => h
  case h :: t   => math.max(h, maxOf(t))
}

@main def run(): Unit =
  println(maxOf(List(3, 9, 2, 7)))  // 9

Schnelltest

Testen Sie Ihr Verständnis rekursiver Strukturen.

Zusammenfassung

Rekursion löst ein Problem, indem sie es auf eine kleinere Instanz seiner selbst reduziert.

Jede rekursive Funktion benötigt einen Basisfall zum Beenden und einen rekursiven Schritt, der die Eingabe auf diesen Basisfall zubewegt.

Listen mit ihrer Struktur aus Nil sowie Kopf und Rest eignen sich ideal, um rekursives Denken zu üben. Achten Sie bei sehr großen Eingaben auf die Stack-Tiefe.

Häufig gestellte Fragen

Ist die Lektion „Rekursiv denken“ kostenlos?

Ja — der vollständige Text von „Rekursiv denken“ 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 „Rekursiv denken“?

Abbruchfälle und rekursive Schritte. 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 1 von 4.

Wie lange dauert die Lektion „Rekursiv denken“?

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