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{align*} n! := n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1 \end{align*} 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{align*} n! = \begin{cases} n \cdot (n-1)! & \textnormal{ if } n \geq 1, \\ 1 & \textnormal{ else.} \end{cases} \end{align*} 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!

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 \(f\) selbst ein Ausdruck ist, in welchem Funktionsaufrufe von \(f\) vorkommen.
Tip. Wenn Sie eine Funktion \(f(n)\) programmieren wollen (wie oben zum Beispiel die Funktion \(n \mapsto n!)\) und Sie das Gefühl haben, dass das nicht direkt geht (direkt wäre zum Beispiel \(n \mapsto n \cdot (n-1))\), dann brauchen Sie wahrscheinlich Rekursion (in Java können Sie alternativ Schleifen verwenden). Gehen Sie wie folgt vor:
  1. Überlegen Sie sich, für welche kleinen Werte von \(n\) Sie das Ergebnis kennen (für \(n!\) wäre das zum Beispiel \(0! =1\) oder \(1! = 1\).
  2. Überlegen Sie sich, wie Sie \(f(n)\) aus Ausdruck schreiben können, in dem \(f(n-1)\) vorkommt.
Übungsaufgabe Betrachten Sie die Funktion \begin{align*} g: \mathbb{N} & \rightarrow \mathbb{N} \\ n & \mapsto \sum_{i=1}^n i^2 \end{align*} Also \(g(n) = 1 + 4 + 9 + \cdots + n^2\). Schreiben Sie eine rekursive Funktion sumOfSquaresUpTo : Int -> Int in Elm. Gehen Sie wie folgt vor: offensichtlich gilt \begin{align*} g (1) = 1 \end{align*} und auch \begin{align*} g(0) = 0 \end{align*} da wir für \(n=0\) gar keine Zahlen aufsummieren (und die leere Summe 0 ergibt). Nun müssen wir irgendwie versuchen, \(g(n)\) als Ausdruck mithilfe von \(g(n-1)\) zu schreiben. Klar: \begin{align*} g(n) = g(n-1) + n^2 \end{align*} Also, als mathematische Fallunterscheidung geschrieben: \begin{align*} g(n) = \begin{cases} g(n-1) + n^2 & \textnormal{ if $n \geq 1$,} \\ 0 & \textnormal{ else.} \end{cases} \end{align*} Übernehmen Sie nun diese beiden Fälle direkt in einen if-Ausdruck und schreiben eine rekursive Funktion sumOfSquaresUpTo : Int -> Int, die \(g\) berechnet.
Übungsaufgabe Schreiben Sie eine rekursive Funktion exp : Int -> Int, die \(f: n \mapsto 2^n\) für natürliche Zahlen berechnet (wobei wir annehmen, dass \(n \geq 0\) gilt). Schreiben Sie zuerst \(f\) als Fallunterscheidung: \begin{align*} f(n) & = \begin{cases} \textnormal{ irgendein einfacher Ausdruck} & \textnormal{ if $n = $ irgendein kleiner Wert} \\ \textnormal{ ein Ausdruck, in dem $f(n-1)$ vorkommt} & \textnormal{ else.} \end{cases} \end{align*} Schreiben Sie dann den Elm-Code.

Die Collatz-Vermutung

Wenn Sie für eine Funktion \(f(n)\) einen rekursiven Code schreiben, dann müssen Sie nicht immer einen Ausdruck finden, der \(f(n)\) mithilfe von \(f(n-1)\) berechnet. Oft wird es auch so etwas wie \(f(n-2)\) oder \(f\left(\floor{\frac{n}{2}}\right)\) sein. Also etwas, das kleiner ist als \(f\). Dann ist ja garantiert, dass Sie irgendwann fertig werden. Rein theoretisch können Sie natürlich auch für \(f(n)\) einen Ausdruck schreiben, in dem \(f(2n)\) 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:

\begin{align*} {\rm collatz}: \mathbb{N} & \rightarrow \mathbb{N} \\ n & \mapsto \begin{cases} n/2 & \textnormal{ if $n$ even,} \\ 3n+ 1 & \textnormal{ if $n$ odd.} \end{cases} \end{align*}

Interessant wird es, wenn Sie mit einer Zahl anfangen, sagen wir \(n=11\) und die Funktion \({\rm collatz}\) wieder und wieder anwenden:

\begin{align*} 11 \mapsto 34 \mapsto 17 \mapsto 52 \mapsto 26 \mapsto 13 \mapsto 40 \mapsto 20 \mapsto 10 \mapsto 5 \mapsto 16 \mapsto 8 \mapsto 4 \mapsto 2 \mapsto 1 \mapsto 4 \mapsto 2 \mapsto 1 \dots \end{align*}

Klar, wenn wir einmal bei 1 ankommen, dann geraten wir in eine Dauerschleife \(1, 4, 2, 1, \dots\). 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 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 Schreiben Sie eine rekursive Funktion collatzUntilOne : Int -> Int, die zählt, wie oft man die Funktion \({\rm collatz}\) 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 \(n-1\) als Argument, sondern eventuell mit \(3n+1\), 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 \begin{align*} {\rm prime}: \mathbb{N} \rightarrow \{\texttt{True}, \texttt{False}\} \end{align*} implementieren können, die überprüft, ob die Eingabe \(n\) eine Primzahl ist. Ich wüsste nicht, wie man \({\rm prime}(n)\) einfach als Ausdruck mithilfe von \({\rm prime } (n-1)\) oder \({\rm prime } (n-2)\) oder generell \({\rm prime } (k)\) für ein kleines \(k\) schreiben sollte. Wie implementieren wir dies nun? Wir definieren erst eine Helfer-Funktion \begin{align*} {\rm hasDivisorBetween2andK} : \mathbb{N} \times \mathbb{N} \rightarrow \{\texttt{True}, \texttt{False}\} \ , \end{align*} wobei \({\rm hasDivisorBetween2andK}(n,k) \) den Wert True ergeben soll, wenn \(n\) einen Teiler \(d\) hat, der mindestens 2 und höchstens \(k\) 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 \({\rm hasDivisorBetween2andK} (n,k)\) für kleine Werte von \(k\) kennen. Klar:

\begin{align*} {\rm hasDivisorBetween2andK} (n,1) = \texttt{False} \ . \end{align*}

Ein Teiler \(d\) kann ja nicht \(d \leq 1\) und \(d \geq 2\) sein! Können wir für größere \(k\) den Ausdruck \({\rm hasDivisorBetween2andK} (n,k)\) irgendwie mithilfe von \({\rm hasDivisorBetween2andK} (n,k-1)\) schreiben? Klar! Wenn \(k\) selbst ein Teiler ist, dann ist die Antwort \(\texttt{True}\). Ansonsten ist die Antwort die gleiche, die es auch für \(k-1\) ist. Also:

\begin{align*} {\rm hasDivisorBetween2andK} (n,k) & = \begin{cases} \texttt{True} & \textnormal{ if $k$ divides $n$} \\ {\rm hasDivisorBetween2andK} (n,k-1) & \textnormal{ else.} \end{cases} \end{align*}

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 \({\rm prime}(n)\) zu implementieren, testen wir einfach, ob \(n\) keinen Teiler zwischen 2 und \(n-1\) hat. Und ja, bevor wir es vergessen: ob \(n \geq 2\) ist, denn \(1\) ist keine Primzahl: 

prime : Int -> Bool
prime n =
    n >= 2 && not (hasDivisorBetween2andK n (n - 1))
Übungsaufgabe Schreiben Sie eine Funktion, die die abgerundete Wurzel \(\floor{\sqrt{n}}\) 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 \(n\) wegen Rundungsfehlern sogar zu falschen Ergebnissen führen). Definieren wir also \begin{align*} f(n) := \floor {\sqrt{n}} \end{align*} Wir wissen natürlich \(f(0)= 0\) und \(f(1)=1\). Können wir \(f(n)\) irgendwie als Ausdruck mithilfe von \(f(n-1)\) schreiben? Ja, wenn Sie scharf nachdenken. Leichter geht es, wenn Sie wie oben eine Funktion \(g(n,k)\) mit zwei Parametern definieren: \begin{align*} g(n,k) := \max \{i \in \{1, \dots, k\} \ | \ i^2 \leq n\} \ . \end{align*} In Worten: \(g(n,k)\) liefert Ihnen die größte Zahl \(i\), die kleiner ist als \(k\) und für die \(i^2 \leq n\) gilt. Überzeugen Sie sich, dass \(g(n,n) = \floor{\sqrt{n}}\) gilt. Implementieren Sie jetzt \(g(n,k)\) in Elm. Sie werden wohl, ähnlich wie für hasDivisorBetween2andK Rekursion über den zweiten Parameter \(k\) benötigen.