Rekursion ist eine weitere, mächtige Kontrollstruktur im Zusammenhang mit Funktionen. Eine Funktion ist rekursiv, wenn diese sich selbst zur Ermittlung des Ergebnisses wieder aufruft.
Das wohl bekannteste Beispiel für die Rekursion ist die Berechnung der Fakultät.
Die Fakultät lässt sich für ganzzahlige, positive Werte (inkl. 0) berechnen.
Um die Fakultät mathematisch auszudrücken, schreiben wir hinter der Zahl, dessen
Fakultät wir berechnen wollen ein Ausrufezeichen. Die Fakultät von vier schreiben wir also
4!
Die Fakultät eines Wertes x ergibt sich aus der Multiplikation von x * (x-1)!,
solange wiederholt, bis x gleich 0 ist. Die Ergebnis Fakultät von 0 ist definiert mit dem Ergebnis 1.
4! = 4 * 3! = 4 * 3 * 2! = 4 * 3 * 2 * 1! = 4 * 3 * 2 * 1 * 0! = 4 * 3 * 2 * 1 * 1 = 24
Um die Eleganz der rekursiven Lösung besser beurteilen zu können, schauen wir uns zunächst eine imperative Lösung mithilfe einer for-Schleife an.
object ImperativeFakultaet {
def main(args: Array[String]): Unit = {
println(fakultaet(4))
}
def fakultaet(value: Int): Int = {
var result = 1
for (i <- 1 to value) result = result * i
result
}
}
Wie wir sehen, lässt sich die Berechnungsvorschrift der Funktion
fakultaet nicht einfach im Quelltext wieder erkennen.
Anders sieht dies bei der rekursiven Lösung aus, die wir uns
nun anschauen wollen.
object RekursiveFakultaet {
def main(args: Array[String]): Unit = {
println(fakultaet(4))
}
def fakultaet(value: Int): Int = if (value == 0) 1 else value * fakultaet(value-1)
}
Bei der rekursiven Lösung passt die entsprechende Funktion in eine Zeile. Auch die Rechenvorschrift zur Berechnung der Fakultät ist in der rekursiven Form besser zu erkennen.
Auffallend ist auch, dass wir bei einer rekursiven Funktion den Rückgabetyp angeben müssen. Der Compiler ist nicht in der Lage den Rückgabetyp einer rekursiven Funktion automatisch zu ermitteln, da dieser Typ wiederum vom eigenen Ergebnis abhägig ist.
Lesen wir etwas über Rekursion oder Diskutieren wir mit anderen Entwicklern über Rekursion, so verwenden wir für die einzelnen Bestandteile einer rekursiven Funktion (Methode) unterschiedliche Namen.
Die eigentliche Funktion, die sich selber aufruft bezeichnen wir als (wie anders erwartet) als "rekursive Funktion". Der Teil der Funktion, welche die Funktion wieder aufruft, bezeichnen wir als "rekursiver Fall" (engl. recursive case). Der Teil, welcher die Funktion nicht wieder aufruft, bezeichnen wir als Basisfall (engl. base case).
Jede rekursive Funktion muss mindestens einen "rekursiven" und einen "Basis" - Fall haben. Ohne rekursiven Fall würde sich die Funktion nicht selber aufrufen und wäre demnach nicht rekursiv. Eine Funktion, ohne Basisfall, würde sich immer wieder selbst aufrufen und würde in einer Endlosschleife enden, was in den allermeisten Fällen nicht gewünscht ist.
Schauen wir uns nun nochmals die Funktion fakultaet an und identifizieren den "rekursiven"
und den Basisfall.
def fakultaet(value: Int): Int = if (value == 0) 1 else value * fakultaet(value-1)
Im Beispiel ist if (value == 0) 1 der Basisfall und else value * fakultaet(value-1)
der rekursive Fall.
Zunächst einmal eine kurze Klärung, was Endrekursion (engl. tail recurion) bedeutet. Eine Funktion
ist endrekursiv, wenn die letzte Operation die in der Funktion ausgeführt wird, der rekursive
Aufruf ist. Zu beachten ist hier, dass es nicht ausreicht, dass die letzte Zeile (das letzte Element) einer
Funktion der rekursive Aufruf ist, sondern auch keine weiteren Operationen stattfindet.
Im obigen Beispiel RekursiveFakultaet ist die letzte Operation nicht der rekursive
Aufruf, sondern die Multiplikation des Ergebnisses mit value.
Aber warum sollen wir Funktionen endrekursiv definieren? Der Grund liegt darin, dass bei nicht endrekursiven Aufrufen jedes Mal ein neuer Stack-Frame erzeugt wird, was Zeit- und speicherintensiv ist. Ein Endrekursiver Aufruf wird jedoch vom Compiler in eine Iteration optimiert, die schneller ist und auch nicht den hohen Speicherbedarf aufweist.
Das nachfolgende Beispiel zeigt die Berechnung der Fakultät in Endrekursiver Form.
Hierzu wird eine Funktion innerhalb der Funktion fakultaet definiert, welche die
Berechnung durchführt. Die eigentliche Berechnung der Fakultät findet im
rekursiven Aufruf der Berechnungsfunktion statt.
object EndRekusriveFakultaet {
def main(args: Array[String]): Unit = {
println(fakultaet(4))
}
def fakultaet(value: Int): Int = {
def fakultaetCalc(result: Int,n: Int): Int = {
if (n == 0) result
else fakultaetCalc(n*result,n-1)
}
fakultaetCalc(1,value)
}
}
@tailrec
Nicht immer ist es einfach zu erkennen, ob eine Funktion endrekursiv ist. Auch ist
wünschenswert, dass wir nicht später eine ursprünglich
endrekursive Funktion, in eine Funktion mit "einfacher" Rekursion
verwandeln. Hier hilft uns die Annotation @tailrec weiter.
Setzen wir diese Annotation vor einer vermeintlich endrekursiven Funktion,
prüft der Compiler, ob tatsächlich eine Endrekursion vorliegt
und die Methode entsprechend optimiert werden kann. Bevor wir die Annotation
verwenden können, müssen wir diese erst z.B. mit
import scala.annotation.tailrec in den Sichtbarkeitsbereich
holen.
Das nachfolgende Beispiel zeigt die endrekursive Berechnung der Fakultät
mit @tailrec Annotation.
object EndRekusriveFakultaet {
def main(args: Array[String]): Unit = {
println(fakultaet(4))
}
def fakultaet(value: Int): Int = {
import scala.annotation.tailrec // --- import of @tailrec annotation ---
@tailrec // ------------------ @tailrec annotation -------------
def fakultaetCalc(result: Int,n: Int): Int = {
if (n == 0) result
else fakultaetCalc(n*result,n-1)
}
fakultaetCalc(1,value)
}
}
Ist eine Funktion nicht endrekursiv und mit der @tailrec Annotation
versehen, erhalten wir vom Compiler eine Fehlermeldung
could not optimize @tailrec annotation method ... .
Heiko Seeberger
http://it-republik.de/jaxenter/
Advanced Scala: Tail Recursion und Optimierung