2. Elm

2.6 Verzweigende Rekursion

Rekursion ist, wenn im Funktionskörper einer Funktion $f$ wiederum ein Aufruf von $f$ als Unterausdruck vorkommt. Warum Singular? Natürlich können auch mehrere Aufrufe von $f$ vorkommen. Paradebeispiel sind die Fibonacci-Zahlen. Dies ist die bekannte Zahlenfolge

\begin{align*} 0, 1, 1, 2, 3, 5, 8, 13, 21, \dots \end{align*}

die mit $0,1$ beginnt, und wo ab da jedes Glied die Summe seiner zwei Vorgänger ist. Mathematisch:

\begin{align*} F_0 & := 0 \\ F_1 & := 1 \\ F_n & := F_{n-2} + F_{n-1} \textnormal{ für alle $n \geq 2$} \end{align*}

Übungsaufgabe Schreiben Sie eine Funktion fib : Int -> Int in Elm, die diese Funktion berechnet, bei Eingabe von $n$ also $F_n$ zurückgibt.

Meine Lösung

fib : Int -> Int
fib n =
    if n == 0 then
        0

    else if n == 1 then
        1

    else
        fib (n - 1) + fib (n - 2)

Die Fibonacci-Zahlen spielen bei der Analyse gewissen Algorithmen eine Rolle. Daher werden Sie Ihnen im dritten Semester in Algorithmen und Komplexität (AuK) wohl wieder begegnen. Uns im Moment dienen sie dazu, gewisse Programmierprinzipine zu erklären und zu üben. Obwohl wir in diesem Semester nur am Rande auf Laufzeitkomplexität blicken (auch hierfür siehe AuK), so sollten wir sie auch nicht ganz aus dem Blick verlieren. Rufen Sie mal meinen (oder Ihren) Code fib n auf für verschiedene Werte von $n$, beispielsweise $n = 30, 35, 40, 45, 50$ und schauen, wie sich die Laufzeit entwickelt. Um die Laufzeit einer sich verzweigenden Funktion zu verstehen, ist es nützlich, den Rekursionsbaum zu zeichnen.

Der Rekursionsbaum

Hier nochmal mein Code für fib n:

fib : Int -> Int
fib n =
    if n == 0 then
        0

    else if n == 1 then
        1

    else
        fib (n - 1) + fib (n - 2)

In einer rekursiven Funktion kann ein Aufruf f n weitere Unteraufrufe versachen. In unserem Konkreten Beispiel verursacht fib n zwei weitere Aufrufe: fib (n-1) und fib (n-2), beides in Zeile 87. Diese verursachen wiederum weitere Aufrufe, bis $n$ klein genug geworden ist, also 1 oder 0. Beachten Sie die Ähnlichkeit zum Prozess einer Zellteilung! Wir können das ganze als Baum darstellen:

In der Informatik wachsen Bäume grundsätzlich von oben nach unten. Beachten Sie, dass die Knoten, die mit fib 1 oder fib 0 beschriftet sind, selbst keine Kinder haben; das ist ja auch richtig, denn sie erzeugen auch keine weiteren rekursiven Aufrufe, da Sie in Zeile 81 oder 84 enden und die Semantik der if-Konstruktion verhindert, dass Zeile 87 ausgewertet wird.

Übungsaufgabe Zeichnen Sie den Rekursionsbaum von fib 5.

Übungsaufgabe Wieviele mit fib 1 beschriftete Blätter hat der Rekursionsbaum von fib n?

Wir betrachten eine weitere Funktion, die ich mir extra für diese Vorlesung ausgedacht habe, und die ich mangels eines besseren Namens weird (Englisch für eigenartig) genannt habe. In der mathematischen Notation kürze ich sie mit $W(n)$ ab.

\begin{align*} W : \mathbb{N} & \rightarrow \mathbb{N} \\ n & \mapsto \begin{cases} 0 & \textnormal{ if $n=0$, }\\ W(n-1) + n & \textnormal{ if $n \geq 1$ and $W(n-1)$ odd}\\ \frac{1}{2} \, W(n-1) + 1 & \textnormal{ else, i.e., if $n \geq 1$ and $W(n-1)$ even.} \end{cases} \end{align*}

Übungsaufgabe Implementieren Sie weird.

Meine Lösung

weird : Int -> Int
weird n =
    if n == 0 then
        0

    else if modBy 2 (weird (n - 1)) == 1 then
        n + weird (n - 1)

    else
        weird (n - 1) // 2 + 1

Übungsaufgabe Testen Sie Ihren bzw. meinen Code, indem Sie weird n für $n = 25, 26, 27, 28, 29, 30$ aufrufen. Fällt Ihnen etwas auf?

Handelt es sich bei der Rekursion um verzweigende Rekursion? Strenggenommen ja, denn der Aufruf von weird 10 erzeugt einen Aufruf (von weird 9) in Zeile 99, und dann nochmal einen, entweder in Zeile 100 oder in Zeile 103.

Übungsaufgabe Zeichnen Sie den Rekursionsbaum für weird 3. Beachten Sie, dass jeder Aufruf für $n \geq 1$ zwei rekursive Aufrufe (mit $n-1$) nach sich zieht.

Ist das vertretbar? Man kann ja argumentieren, dass sich die Rekursion gar nicht verzweigen müsste, weil man das Ergebnis $W(n-1)$ ja wiederverwenden könnte, anstatt es nochmal zu berechnen. Betrachten Sie hierzu meinen Java-Code:

public class Recursion {
	public static int weirdJava (int n) {
		if (n == 0) {
			return 0;
		}
		else {
			int wNminus1 = weirdJava(n-1);
			if (wNminus1 % 2 == 1) {
				return wNminus1 + n; 
			}
			else {
				return wNminus1 / 2 + 1;
			}
		}  
...
 style='counter-set: listing 23;'}

In Zeile 7 berechnen wir $W(n-1)$ und merken es uns in der Variable wNminus1. Somit brauchen wir nur einen rekursiven Aufruf. Die Auswertung von weirdJava(n) in Java erzeugt also insgesamt n weitere Aufrufe (für $i = 0, 1, \dots, n-1$), während in Elm die Auswertung von weird n zwei Aufrufe von weird (n-1) erzeugt, vier von weird (n-2) und schließlich $2^n$ Aufrufe von weird 0. Um also beispielsweise $W(40)$ zu berechnen, braucht Java insgesamt 41 Aufrufe. Unser Elm-Code braucht $1 + 2 + 4 + 8 + \dots + 2^{40} = 2^{41} - 1$.

Java ist unbestreitbar schneller als Elm. Allerdings ist der Unterschied zwischen weird und weirdJava nicht nur der Unterschied zwischen dem schnellen (weil hardware-näheren) Java und dem langsameren (weil hardware-ferneren und eher für Web-Frontends gedachten) Elm; sondern es ist ein Unterschied zwischen einem effizienten und einem ineffizienten Algorithmus. Können wir also unseren Elm-Code effizienter machen und irgendwie das Zwischenergebnis wiederverwenden?

Zwischenergebnisse wiederverwenden mit Helfer-Funktionen

Versuchen wir, den Code von weird effizienter zu machen, und zwar allein mit den Techniken, die wir bereits gelernt haben. Die erste Beobachtung ist, dass der Java-Code in Zeile 8-14 keinen rekursiven Aufruf enthält, sondern einfach wNminus1 weiterverarbeitet. Wir können also in Elm auch eine Funktion weirdHelper schreiben, die diesen Teil übernimmt:

weirdHelper : Int -> Int -> Int
weirdHelper wNminus1 n =
    if modBy 2 wNminus1 == 1 then
        wNminus1 + n

    else
        wNminus1 // 2 + 1

Nun schreiben wir einfach eine rekursive Funktion weirdWithHelper, die rekursiv $W(n-1)$ berechnet und dann weirdHelper aufruft; die also im Prinzip die Java-Zeilen 2-7 in Elm implementiert:

weirdWithHelper : Int -> Int
weirdWithHelper n =
    if n == 0 then
        0

    else
        weirdHelper (weirdWithHelper (n - 1)) n

Der rekursive Aufruf weirdWithHelper (n-1) wird also nur einmal ausgewertet; das Ergebnis wird dann als Argument der Funktion weirdHelper übergeben (dort als Parameter mit Namne wNminus1 bekannt); dass wNminus1 im Code von weirdHelper mehrfach verwendet wird, spielt keine Rolle; der Ausdruck ist bereits ausgewertet worden, zu einer Zahl, und kann "kostenlos" wiederverwendet werden.

Übungsaufgabe Führen Sie weird n und weirdWithHelper n für $n = 25, 26, 27, 28, 29$ aus und spüren Sie den Laufzeitunterschied.

Selbst weirdWithHelper 100 ist kein Problem, während weird 100 mindestens $2^{100}$ rekursive Aufrufe erzeugen würde (man sagt gerne, $2^{100}$ ist größer als die Anzahl der Atome im Universum, was verdeutlichen soll, dass so eine Zahl als Laufzeit eines Algorithmus nicht akzeptabel sein kann). .

Zwischenergebnisse mit `let`

Wir haben also gesehen, dass wir Zwischenergebnisse "speichern" können, indem wir die Weiterverarbeitung in einer Helferfunktion auslagern. In der Praxis ist das aber meist unbequem, und daher kann man in Elm Zwischenergebnisse speichern (und einem Bezeichner zuweisen), ähnlich wie wir es in Java in Zeile 7 mit int wNminus1 = weirdJava(n-1); getan haben. Dies geht mit der let ... in ...-Konstruktion:

weirdWithLet : Int -> Int
weirdWithLet n =
    if n == 0 then
        0

    else
        let
            y : Int -- Bezeichner für ein Zwischenergebnis deklarieren
            y =
                weirdWithLet (n - 1) -- Zwischenergebnis berechnen und im Bezeichner speichern
        in
        if modBy 2 y == 1 then
            y + n

        else
            y // 2 + 1

Im allgemeinen sieht eine let-Konstruktion wie folgt aus:

let 
    identifier1 : Type1 
    identifier1 = expression1 
    ...
    identifierN : TypeN
    identifierN = expressionN 
in 
finalExpression

In finalExpression dürfen dann die Bezeichner identifier1, ..., identifierN vorkommen. Alles, was Sie im Top-Level in Ihrer Programmdatei definieren, also auch Funktionen etc., dürfen Sie innerhalb eines let-Blocks definieren.

Finbonacci-Zahlen ohne Verzweigung

Können wir einen ähnlichen Trick bei den Fibonacci-Zahlen anwenden, um die sich verzweigende Rekursion in eine "lineare" Rekursion umzuwandeln? Ein tatsächliches Problem ist hierbei, dass wir tatsächlich zwei Vorergebnisse benötigen, um $F_n$ zu berechnen, nämlich $F_{n-1}$ und $F_{n-2}$. Betrachten wir den Java-Code:

	public static int fib (int n) {
		int a = 0; 
		int b = 1; 
		for (int i = 0; i < n; i++) {
			int temp = a+b; 
			a = b; 
			b = temp;
		}
		return a;
	}

Wir führen zwei lokale Variable, a und b. In jedem Schritt wird das Paar $(a,b)$ durch das Paar $(b, a+b)$ ersetzt. Wir können nun also in Elm eine Funktion schreiben, die nicht $F_n$, sondern das Paar $(F_n, F_{n+1})$ zurückgibt. Geht das? Gibt es Paare in Elm? Probieren wir es aus:

(1.0, 2.0)                        
(1.0, 2.0) : (Float, Float)

Wir können ganz einfach mit Klammern-Notation Paare definieren. Das geht mit beliebigen Typen:

n : Int
n = 1
(n, "Montag")                        
(1, "Montag") : (Int, String)

Wir können an das erste und zweite Element ran mit Tuple.first und Tuple.second:

pair = ("Montag", "Monday")                        
Tuple.first pair
"Montag" : String

Etwas zu dem Wort Tuple, auf Deutsch Tupel. Das Wort ist aus der lateinischen Endung -tuplus abgeleitet, zum Beispiel quintuplus (fünffach), septuplus (siebenfach). Ein Tupel bezeichnet eine endliche Reihe von Zahlen, wobei die Reihenfolge wichtig ist. Das unterscheidet beispielsweise das 4-Tupel $(1,6,3,4)$ von der Menge $\{1,6,3,4\}$. Eine Menge interessiert sich nur dafür, welche Elemente drin sind, ohne Reihenfolge, ohne Häufigkeit. Daher sind \begin{align*} \{1,6,3,4\} \\ \{1,3,4,6\} \\ \{1,1,3,4,6,4\} \end{align*} alles die gleiche Menge, während \begin{align*} (1,6,3,4) \\ (1,3,4,6) \\ (1,1,3,4,6,4) \end{align*} alles verschiedene Tupel sind. Hier also mein Code für die Fibonacci-Zahlen mit Tupeln. Die Funktion fibPair liest eine ganze Zahl n ein und gibt das Paar $(F_n, F_{n+1})$ zurück:

fibPair : Int -> ( Int, Int )
fibPair n =
    if n == 0 then
        ( 0, 1 )

    else
        let
            previousPair : ( Int, Int )
            previousPair =
                fibPair (n - 1)

            a : Int
            a =
                Tuple.first previousPair

            b : Int
            b =
                Tuple.second previousPair
        in
        ( b, a + b )

Sehen Sie nun: ein Aufruf von fibPair n zieht einen rekursiven Aufruf nach sich, nämlich fibPair (n-1). Insgesamt werden also nur $n+1$ Aufrufe getätigt (für $i = 0,1, \dots, n)$. Da sich die Nutzer nicht für unsere Implementierungsdetails interessieren, sollten wir Ihnen eine Wrapper-Funktion zur Verfügung stellen, die einfach aus $n$ das Ergebnis $F_n$ berechnet und die Verwendung der Tupel einkapselt:

fibFast : Int -> Int
fibFast n =
    Tuple.first (fibPair n)

Übungsaufgabe Vergleichen Sie die Laufzeiten von fibFast und fib. Testen Sie für $n = 25, 30, 35, 40$ und so weiter.