2. Elm

2.5 Rekursion

Mit Funkionen und Fallunterscheidungen haben Sie schon zwei der wichtigsten Prinzipien der Programmierung kennengelernt. Eine Sache haben Sie aber vielleicht bisher vermisst: Schleifen. Wenn Sie bereits in anderen Sprachen programmiert haben, dann sind Ihnen bestimmt Schleifen begegnet, also Anweisungen an das Programm, eine Abfolge von Schritten mehrfach zu wiederholen. Als Beispiel betrachten wir die Fakultätsfunktion (auf Englisch factorial):

\begin{array}{r} n! := n \cdot (n - 1) \cdot (n - 2) \dots 2 \cdot 1 \end{array}

also beispielsweise

7! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5040

. Wie können wir in Elm eine Funktion schreiben, die das berechnet? Schleifen gibt es nicht. Aber das, was wir bis jetzt kennengelernt haben, recht (fast) aus. Nämlich folgende Prinzipien:

Einen Funktionsaufruf wie f 7 auszuwerten heißt, im Körper von f den Parameter durch den Ausdruck 7 (das Argument) zu ersetzen.
Im Körper von Funktionen dürfen als Ausdrücke wiederum Funktionsaufrufe drinstehen.

Im konkreten Fall von

n!

beginnen wir mit der mathematischen Identität

\begin{array}{r} n! = {\begin{cases} n \cdot (n - 1)! & if n \geq 1, \\ 1 & else. \end{cases} \end{array}

Letzteres kann man entweder als Konvention betrachten oder noch weiter rechtfertigen. Akzeptieren wir es erst einmal so. Wenn wir also

(n - 1)!

irgendwie berechnen könnten, dann könnten wir

n

draufmultiplizieren und hätten nun

n!

. Eröffnen Sie eine neue Datei und speichern Sie sie ab als Recursion.elm im Order PP/elm/src. Dann kopieren Sie folgenden Quelltext hinein.

module Recursion exposing (..)


factorial : Int -> Int
factorial n =
    if n == 0 then
        1

    else
        n * factorial (n - 1)

Der revolutionäre Gedanke steckt in Zeile 10. Dieser Ausdruck enthält seinerseits einen Funktionsaufruf, und zwar auf die Funktion selbst. Wir nennen dies Rekursion. Geht das / dürfen wir das? Werten wir mal den Ausdruck factorial 3 per Hand aus!

f 3

if 3 == 0 then 1 else 3 * factorial (3 - 1)

if False then 1 else 3 * factorial (3 - 1)

3 * (factorial (3 - 1))

3 * (factorial 2)

3 * (if 2 == 0 then 1 else 2 * factorial (2 - 1)

3 * (if False then 1 else 2 * factorial (2 - 1)

3 * 2 * factorial (2 - 1)

3 * 2 * factorial 1

3 * 2 * (if 1 == 0 then 1 else 1 * factorial (1 - 1))

3 * 2 * (if False then 1 else 1 * factorial (1 - 1))

3 * 2 * 1 * factorial (1 - 1)

3 * 2 * 1 * factorial 0

3 * 2 * 1 * (if 0 == 0 then 1 else factorial (0 - 1))

3 * 2 * 1 * (if True then 1 else factorial (0 - 1))

3 * 2 * 1 * 1

6

Im Prinzip steht nichts dagegen, im Körper von factorial einen Ausdruck zu schreiben, der factorial selbst wieder beinhaltet. Solange wir sicher sind, dass es irgendwann "zu Ende geht". Entscheidend ist dabei unter Anderem, wie Elm eine if-Konstruktion auswertet, insbesondere die zeitliche Reihenfolge. Betrachten wir noch einmal die Syntax von if:

                        if condition then expression1 else expression2

Hierbei muss condition ein Ausdruck vom Typ Bool sein. Will Elm eine if-Konstruktion auswerten, so wird zuerst der Ausdruck condition ausgewertet. Ergibt dies True, so wird expression1 ausgewertet; ergibt es False, dann wird expression2 ausgewertet. Entscheidend ist, dass der andere Ausdruck ignoriert und gar nicht erst ausgewertet wird. Dies rettet uns im Ausdruck

3 * 2 * 1 * (if 0 == 0 then 1 else factorial (0 - 1))

Elm versucht nicht, den Ausdruck expression2, also factorial (0 - 1) auszuwerten. Dies würde nämlich dann in der Tat verhindern, dass wir jemals fertigwerden.

Rekursive Funktionen schreiben

Rekursion heißt, dass eine Funktion sich selbst aufruft; dass also der Körper einer Funktion

selbst ein Ausdruck ist, in welchem Funktionsaufrufe von

vorkommen.

Tip. Wenn Sie eine Funktion

programmieren wollen (wie oben zum Beispiel die Funktion

und Sie das Gefühl haben, dass das nicht direkt geht (direkt wäre zum Beispiel

, dann brauchen Sie wahrscheinlich Rekursion (in Java können Sie alternativ Schleifen verwenden). Gehen Sie wie folgt vor:

Überlegen Sie sich, für welche kleinen Werte von Sie das Ergebnis kennen (für wäre das zum Beispiel oder .
Überlegen Sie sich, wie Sie aus Ausdruck schreiben können, in dem vorkommt.

Übungsaufgabe 2.5.1 Betrachten Sie die Funktion

Also

. Schreiben Sie eine rekursive Funktion sumOfSquaresUpTo : Int -> Int in Elm. Gehen Sie wie folgt vor: offensichtlich gilt

und auch

da wir für

gar keine Zahlen aufsummieren (und die leere Summe 0 ergibt). Nun müssen wir irgendwie versuchen,

als Ausdruck mithilfe von

zu schreiben. Klar:

Also, als mathematische Fallunterscheidung geschrieben:

Übernehmen Sie nun diese beiden Fälle direkt in einen if-Ausdruck und schreiben eine rekursive Funktion sumOfSquaresUpTo : Int -> Int, die

berechnet.

Übungsaufgabe 2.5.2 Schreiben Sie eine rekursive Funktion exp : Int -> Int, die

für natürliche Zahlen berechnet (wobei wir annehmen, dass

gilt). Schreiben Sie zuerst

als Fallunterscheidung:

Schreiben Sie dann den Elm-Code.

Die Collatz-Vermutung

Wenn Sie für eine Funktion einen rekursiven Code schreiben, dann müssen Sie nicht immer einen Ausdruck finden, der mithilfe von berechnet. Oft wird es auch so etwas wie oder sein. Also etwas, das kleiner ist als . Dann ist ja garantiert, dass Sie irgendwann fertig werden. Rein theoretisch können Sie natürlich auch für einen Ausdruck schreiben, in dem vorkommt. Dann ist es aber Ihre Pflicht, zu argumentieren, dass man irgendwann "fertig" wird. Ein Beispiel hierfür ist die berühmte Collatz-Vermutung. Wir definieren folgende Funktion:

Interessant wird es, wenn Sie mit einer Zahl anfangen, sagen wir und die Funktion wieder und wieder anwenden:

Klar, wenn wir einmal bei 1 ankommen, dann geraten wir in eine Dauerschleife . Die Frage ist nun, ob wir immer bei 1 ankommen, egal, mit welcher Zahl wir anfangen? Dies ist eine berühmte offene Frage. Es wird unter den Mathematischern allgemein vermutet, dass man immer bei 1 rauskommt. Beweisen können wir das (Stand 2023) aber nicht.

Übungsaufgabe 2.5.3 Schreiben Sie in Elm eine Funktion collatz : Int -> Int, die obige Funktion implementiert.

Tip. Da brauchen Sie keine Rekursion. Das geht mit einer einfachen Fallunterscheidung.

Übungsaufgabe 2.5.4 Schreiben Sie eine rekursive Funktion collatzUntilOne : Int -> Int, die zählt, wie oft man die Funktion

anwenden muss, bis man bei 1 landet. Also

collatzUntilOne 1                                
0 : Int
collatzUntilOne 11                                
14 : Int

Tip. Wenn Sie in Ihrem Code durch 2 dividieren wollen, schreiben Sie n // 2 und nicht n / 2. Der Operator / will Float als Input und gibt Float als Output, was in Ihrem Kontext keinen Sinn macht. Der Operator // will Int als Input und gibt als Output ein Int (das Ergebnis der Division, abgerundet). Beispielsweise:

4 / 2
2 : Float
floor (4/2)
2 : Int
floor (7/2)
3 : Int

Ihre Funktion ruft sich selbst auf, aber nicht mit als Argument, sondern eventuell mit , also einer größeren Zahl. Es ist also nicht gesagt, dass Ihre Funktion jemals terminieren wird. Rein theoretisch könnten Sie in Endlosschleifen geraten. Die Collatz-Vermutung besagt eben gerade, dass dies nicht geschehen wird.

Rekursive Funktionen mit mehreren Parametern

Niemand verbietet Ihnen, Rekursion auch in Funktionen mit mehreren Eingabeparametern anzuwenden. Überlegen wir uns mal, wie wir eine Funktion implementieren können, die überprüft, ob die Eingabe eine Primzahl ist. Ich wüsste nicht, wie man einfach als Ausdruck mithilfe von oder oder generell für ein kleines schreiben sollte. Wie implementieren wir dies nun? Wir definieren erst eine Helfer-Funktion wobei den Wert True ergeben soll, wenn einen Teiler hat, der mindestens 2 und höchstens ist. Beispielsweise

hasDivisorBetween2andK 21 5
True : Bool weil 3 ein Teiler von 21 ist 3 <= 5
hasDivisorBetween2andK 77 6
False : Bool weil 7 der kleinste Teiler ist, und 7 > 6
hasDivisorBetween2andK 77 7
True : Bool weil 7 > 7 ist und das auch zählt

Um das irgendwie rekursiv zu implementieren, überlegen wir uns, ob wir den Wert von für kleine Werte von kennen. Klar:

Ein Teiler kann ja nicht und sein! Können wir für größere den Ausdruck irgendwie mithilfe von schreiben? Klar! Wenn selbst ein Teiler ist, dann ist die Antwort . Ansonsten ist die Antwort die gleiche, die es auch für ist. Also:

Das können wir direkt in Elm-Code übersetzen:

hasDivisorBetween2andK : Int -> Int -> Bool
hasDivisorBetween2andK n k =
    if k <= 1 then
        False

    else if modBy k n == 0 then
        True

    else
        hasDivisorBetween2andK n (k - 1)

Um nun zu implementieren, testen wir einfach, ob keinen Teiler zwischen 2 und hat. Und ja, bevor wir es vergessen: ob ist, denn ist keine Primzahl:

prime : Int -> Bool
prime n =
    n >= 2 && not (hasDivisorBetween2andK n (n - 1))

Übungsaufgabe 2.5.5 Schreiben Sie eine Funktion, die die abgerundete Wurzel

berechnet. Wir könnten natürlich schummeln:

sqrt 17
4.123105625617661 : Float
floor (sqrt 17)
4 : Int

Aber das wäre nicht besonders instruktiv (und könnte für sehr hohe Zahlen wegen Rundungsfehlern sogar zu falschen Ergebnissen führen). Definieren wir also Wir wissen natürlich und . Können wir irgendwie als Ausdruck mithilfe von schreiben? Ja, wenn Sie scharf nachdenken. Leichter geht es, wenn Sie wie oben eine Funktion mit zwei Parametern definieren: In Worten: liefert Ihnen die größte Zahl , die kleiner ist als und für die gilt. Überzeugen Sie sich, dass gilt. Implementieren Sie jetzt in Elm. Sie werden wohl, ähnlich wie für hasDivisorBetween2andK Rekursion über den zweiten Parameter benötigen.