Stufe 2Sprachkern · Lektion 11 von 34

Rekursion

Aktualisiert am 24. September 20263 Min. LesezeitSchritt 6/7 dieser Stufe

Eine Funktion, die sich selbst aufruft, heißt rekursiv. In der funktionalen Programmierung ersetzt Rekursion oft die Schleife mit veränderlichem Zähler. Damit das nicht zum Stapelüberlauf führt, hilft Scala mit der Annotation @tailrec.

Basisfall und Rekursionsschritt

Das klassische Beispiel ist die Fakultät: n! = n · (n − 1)!, und 0! = 1.

def fak(n: Int): BigInt =
  if n == 0 then 1
  else n * fak(n - 1)

fak(5)    // 120
fak(25)   // 15511210043330985984000000

Jede rekursive Funktion braucht zwei Teile:

1. einen Basisfall, der ohne weiteren Aufruf ein Ergebnis liefert (hier n == 0),
2. einen Rekursionsschritt, der das Problem verkleinert und sich selbst aufruft (hier fak(n - 1)).

Fehlt der Basisfall oder wird das Problem nicht kleiner, ruft sich die Funktion endlos auf.

Der Aufrufstapel

Bei jedem Aufruf legt die JVM einen Eintrag auf den Aufrufstapel. fak(4) kann erst rechnen, wenn fak(3) fertig ist, und so weiter. Der Stapel ist begrenzt: Bei einigen tausend bis zehntausend verschachtelten Aufrufen – je nach Einstellung der JVM – bricht das Programm mit einem StackOverflowError ab.

Endrekursion

Eine Funktion ist endrekursiv (englisch tail recursive), wenn der rekursive Aufruf das Allerletzte ist, was sie tut. Bei n * fak(n - 1) ist das nicht der Fall: Nach dem Aufruf muss noch multipliziert werden. Mit einem Akkumulator, der das Zwischenergebnis mitträgt, lässt sich das umbauen:

import scala.annotation.tailrec

def fak(n: Int): BigInt =
  @tailrec
  def schleife(k: Int, acc: BigInt): BigInt =
    if k == 0 then acc
    else schleife(k - 1, acc * k)
  schleife(n, 1)

fak(10_000).toString.length   // 35660 Stellen, kein Stapelüberlauf

Endrekursive Funktionen übersetzt der Scala-Compiler in eine gewöhnliche Schleife – der Stapel wächst nicht. Die Annotation @tailrec ist dabei eine Zusicherung: Ist die Funktion doch nicht endrekursiv, meldet der Compiler einen Fehler, statt still eine langsame, stapelhungrige Version zu erzeugen.

Rekursion über Listen

Listen in Scala sind selbst rekursiv aufgebaut: Eine Liste ist entweder leer (Nil) oder ein Kopf gefolgt von einer weiteren Liste (siehe List). Rekursive Funktionen passen deshalb gut dazu, am lesbarsten mit Pattern Matching:

def summe(xs: List[Int]): Int = xs match
  case Nil          => 0
  case kopf :: rest => kopf + summe(rest)

def laenge[A](xs: List[A]): Int = xs match
  case Nil       => 0
  case _ :: rest => 1 + laenge(rest)

Beide Funktionen sind nicht endrekursiv. Für lange Listen gehören sie deshalb umgebaut – oder, noch besser, durch die fertigen Methoden sum, length und foldLeft ersetzt.

Fibonacci: ein warnendes Beispiel

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

Die Definition ist elegant, aber verheerend langsam: fib(45) löst über zwei Milliarden Aufrufe aus, weil dieselben Werte immer wieder neu berechnet werden. Die endrekursive Variante trägt einfach die letzten beiden Zahlen mit:

def fib(n: Int): BigInt =
  @tailrec
  def los(i: Int, a: BigInt, b: BigInt): BigInt =
    if i == 0 then a else los(i - 1, b, a + b)
  los(n, 0, 1)

fib(90)   // 2880067194370816120

Wann Rekursion, wann nicht?

• Rekursion passt zu rekursiv aufgebauten Daten: Listen, Bäume, verschachtelte Strukturen, Syntaxbäume.
• Collection-Methoden wie map, filter und foldLeft sind für die meisten Aufgaben über Listen kürzer und bereits optimiert.
• Schleifen mit var sind in Scala nicht verboten. In engen, leistungskritischen Stellen sind sie manchmal die pragmatische Wahl.