Rekursionsgrundlagen
Rekursive Funktionen
Rekursionsgrundlagen 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 ist Rekursion?
Rekursion liegt vor, wenn eine Funktion sich selbst aufruft, um eine kleinere Variante desselben Problems zu lösen. Sie eignet sich gut für die funktionale Programmierung und ersetzt viele Schleifen durch selbstreferenzielle Definitionen.
Zwei wesentliche Bestandteile
Jede korrekte rekursive Funktion benötigt:
- einen Basisfall, der die Rekursion beendet,
- einen rekursiven Fall, der sich dem Basisfall nähert.
Ohne einen erreichbaren Basisfall läuft die Rekursion endlos weiter.
Fakultät
Das klassische Beispiel: n! = n * (n-1)!, wobei 0! = 1 als Basisfall dient.
object Main {
def factorial(n: Int): Int =
if (n <= 1) 1
else n * factorial(n - 1)
def main(args: Array[String]): Unit = {
println(factorial(5))
}
}Aufrufabläufe nachvollziehen
Jeder rekursive Aufruf pausiert und wartet auf das innere Ergebnis. factorial(3) wird zu 3 * (2 * (1)) entfaltet. Die Multiplikationen finden statt, wenn die Aufrufe zurückkehren.
object Main {
def factorial(n: Int): Int = {
println(s"entering factorial($n)")
if (n <= 1) 1 else n * factorial(n - 1)
}
def main(args: Array[String]): Unit = {
println("result = " + factorial(3))
}
}Summe einer Liste
Rekursion über eine Liste: Die Summe ist der Kopf plus die Summe des Rests, wobei die Summe der leeren Liste null ist.
object Main {
def sum(xs: List[Int]): Int = xs match {
case Nil => 0
case h :: t => h + sum(t)
}
def main(args: Array[String]): Unit = {
println(sum(List(1, 2, 3, 4)))
}
}Länge einer Liste
Dasselbe Muster berechnet die Länge: Eine leere Liste hat die Länge 0, andernfalls ist die Länge 1 plus die Länge des Rests.
object Main {
def length[A](xs: List[A]): Int = xs match {
case Nil => 0
case _ :: t => 1 + length(t)
}
def main(args: Array[String]): Unit = {
println(length(List("a", "b", "c")))
}
}Der Aufrufstapel
Jeder ausstehende rekursive Aufruf verwendet einen Stack-Frame. Bei tiefer Rekursion werden viele Frames auf dem Stapel angelegt. Bei sehr großen Eingaben kann dadurch der Stapel erschöpft werden und ein StackOverflowError auftreten.
Fibonacci
Bei manchen Problemen verzweigt sich die Rekursion in mehrere rekursive Aufrufe. Fibonacci ruft sich selbst zweimal auf, was elegant, aber hinsichtlich des Aufwands exponentiell ist.
object Main {
def fib(n: Int): Int =
if (n < 2) n
else fib(n - 1) + fib(n - 2)
def main(args: Array[String]): Unit = {
println(fib(10))
}
}Eine Liste umkehren
Mit Rekursion lassen sich neue Strukturen aufbauen: Beim Umkehren wird der Kopf an die umgekehrte Version des Rests angehängt.
object Main {
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case h :: t => reverse(t) :+ h
}
def main(args: Array[String]): Unit = {
println(reverse(List(1, 2, 3)))
}
}Rekursion oder Iteration
Schleifen verändern einen Zähler; Rekursion beschreibt das Problem deklarativ. Beides ist gültig. Rekursion eignet sich besonders für baumförmige Daten und Teile-und-herrsche-Verfahren, aber naive Rekursion kann bei großen linearen Eingaben zu einem Stack-Overflow führen.
Größter gemeinsamer Teiler
Der euklidische Algorithmus ist von Natur aus rekursiv und konvergiert schnell.
object Main {
def gcd(a: Int, b: Int): Int =
if (b == 0) a else gcd(b, a % b)
def main(args: Array[String]): Unit = {
println(gcd(48, 18))
}
}Kurztest
Testen Sie Ihre Grundlagen der Rekursion.
Zusammenfassung
Sie haben die Grundlagen der Rekursion kennengelernt:
- Jede rekursive Funktion benötigt einen Basisfall und einen rekursiven Fall.
- Jeder ausstehende Aufruf verwendet einen Stack-Frame; tiefe Rekursion kann zu einem Überlauf führen.
- Rekursion beschreibt Algorithmen für Listen und Bäume auf natürliche Weise.
Als Nächstes machen Sie Rekursion mit der Annotation @tailrec stapelsicher.
Häufig gestellte Fragen
Ist die Lektion „Rekursionsgrundlagen“ kostenlos?
Ja — der vollständige Text von „Rekursionsgrundlagen“ 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 „Rekursionsgrundlagen“?
Rekursive Funktionen 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 „Rekursionsgrundlagen“?
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
- Rekursionsgrundlagen
- Die tailrec-Annotation
- Akkumulator-Muster
- Trampolining