4. Listen

4.4 Endrekursion

Ich zeige Ihnen nun zwei Weisen, die Funktion tomorrow im Modul Date.elm zu implementieren:

addDays1 : Int -> Date -> Date
addDays1 n date =
    if n == 0 then
        date

    else
        tomorrow (addDays1 (n - 1) date)

Schematisch tut die Funktion dieses:

Wir zählen rekursiv erstmal 999 Tage drauf und rufen zum Schluss noch einmal tomorrow auf. Hier ist eine alternative, fast identische Implementierung:

addDays2 : Int -> Date -> Date
addDays2 n date =
    if n == 0 then
        date

    else
        addDays2 (n - 1) (tomorrow date)

Schematisch tut sie dies:

Funktionieren tun natürlich beide Versionen:

addDays1 2000 {day = 7, month = 11, year = 2023}                        
{ day = 29, month = 4, year = 2029 }
addDays2 2000 {day = 7, month = 11, year = 2023}                        
{ day = 29, month = 4, year = 2029 }
                    

Welche Version finden Sie schöner? Ich finde vielleicht addDays2 schöner, weil sie die Arbeit, die sofort erledigt werden kann (den Aufruf von tomorrow, der keine weiteren rekursiven Aufrufe erzeugt), sofort erledigt, während addDays1 ihn in die Zukunft verschiebt. Und in der Tat, probieren Sie mal folgendes aus:

addDays2 8000 {day = 7, month = 11, year = 2023}
{ day = 2, month = 10, year = 2045 }
addDays1 8000 {day = 7, month = 11, year = 2023}
RangeError: Maximum call stack size exceeded

Vielleicht müssen Sie auf Ihrem Rechner statt 8000 die 20000 eingeben. Um diese Fehlermeldung wirklich zu verstehen, müssten wir über Rechnerarchitektur und Compilerbau sprechen. Aber wir können bereits einen Einblick gewinnen, indem wir uns daran erinnern, wie das Auswerten von Ausdrücken funktionierte: den Körper der Funktion nehmen und die Parameter durch die Argumente ersetzen. Wenn die Argumente selbst Funktionsaufrufe enthalten, dann die zuerst auswerten. Nur vollständig ausgewertete Ausdrücke als Argument übergeben. Das schaut im Folgenden bei addDays1 so aus:

addDays1 1000 {day = 3, month = 10, year = 1990}

tomorrow (addDays1 999 {day = 3, month = 10, year = 1990}) -- weil Zeile 115 aufgerufen wird 

tomorrow (tomorrow (addDays1 998 {day = 3, month = 10, year = 1990}))

tomorrow (tomorrow (tomorrow (addDays1 997 {day = 3, month = 10, year = 1990})))

...

tomorrow (tomorrow (... (tomorrow (addDays1 0 {day = 3, month = 10, year = 1990})) ... ))

tomorrow (tomorrow (... (tomorrow {day = 3, month = 10, year = 1990}) ... ))

tomorrow (tomorrow (... {day = 4, month = 10, year = 1990} ... ))                        
                    

Der Ausdruck wächst also auf eine monströse Größe an, bis in der drittletzten Zeile oben dann addDays1 0 ... steht und der then-Teil, also Zeile 112, aufgerufen wird. Diesen Stapel an Funktionsaufrufen nennt auf Englisch den call stack. Jetzt verstehen Sie auch die Fehlermeldung RangeError: Maximum call stack size exceeded. Der Stapel ist zu groß geworden. Die Laufzeitumgebung von Elm hat eine Maximalgröße. Betrachten wir im Gegensatz dazu den Call Stack von addDays2:

addDays2 1000 {day = 3, month = 10, year = 1990}

addDays2 999 (tomorrow {day = 3, month = 10, year = 1990}) -- hier wurde Zeile 124 aufgerufen

addDays2 999 {day = 4, month = 10, year = 1990} -- weil zuerst der innere Aufruf, der von tomorrow, ausgeführt wird

addDays2 998 (tomorrow {day = 4, month = 10, year = 1990})

addDays2 998 {day = 5, month = 10, year = 1990}

addDays2 997 (tomorrow {day = 5, month = 10, year = 1990})

addDays2 997 {day = 6, month = 10, year = 1990}

Sie sehen: auf dem Stack liegen maximal 2 Aufrufe, nämlich einer von addDays2 und einer von tomorrow. Die Folge ist, dass die Auswertung von addDays2 100000 {day = 3, month = 10, year = 1990} zwar mehr Schritte benötigt als addDays2 52 {day = 3, month = 10, year = 1990}, aber nicht mehr Speicherplatz und vor allem nicht mehr Speicherplatz auf dem call stack.

Es gibt also "schlechte" Rekursion, die den Stack immer weiter wachsen lässt, und "gute", bei der der Stack nicht wächst. Die "gute" nennt man auch Endrekursion, auf Englisch tail recursion. Endrekursion liegt vor, wenn die rekursiv aufgerufene Funktion "ganz außen" aufgerufen wird.

Rekursive Funktionen in Endrekursion umwandeln

Oft können Sie mit ein paar Tricks eine gegebene Funktion in eine endrekursive Funktion umschreiben und somit größere Inputs verarbeiten. Oft geht das mit einer Variable, die ein Zwischenergebnis speichert. Im obigen Fall hatte der Parameter date von addDays2 diese Rolle bereits übernommen. Manchmal müssen wir künstlich eine neue Variable für das Zwischenergebnis einführen. Als Beispiel erinnern Sie sich an die Funktion

Ich implementiere sie nun unter dem Namen sumUpTo.

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

    else
        n + sumUpTo (n - 1)

Das ist keine Endrekursion! Nach dem rekursiven Aufruf von sumUpTo (n-1) in Zeile 102 müssen wir nur weitere Aufgaben erledigen, nämlich n dazuaddieren. Endrekursion jedoch hieße, dass der rekursive Aufruf das endgültige Ergebnis bereits liefert, dass also keine weiteren Aufgaben anfallen. In der Tat ist sumUpTo nicht besonders gut:

sumUpTo 100                        
5050 -- funktioniert immerhin
sumUpTo 12000
RangeError: Maximum call stack size exceeded

Wir können dem Stack beim Wachsen zu schauen:

sumUpTo 12000
12000 + sumUpTo 11999 -- Zeile 133 wird aufgerufen
12000 + 11999 + sumUpTo 11998
12000 + 11999 + 11998 + sumUpTo 11997
12000 + 11999 + 11998 + 11997 + sumUpTo 11996

Wir legen nun explizit eine Zwischenergebnisvariable sumSoFar an, in der wir speichern, wieviel wir bereits aufaddiert haben. Die soll anfangs 0 sein, und dann schaufeln wir n drauf.

sumUpTo2 : Int -> Int -> Int
sumUpTo2 sumSoFar n =
    if n == 0 then
        sumSoFar

    else
        sumUpTo2 (sumSoFar + n) (n - 1)

Nun steht der rekursive Aufruf von sumUpTo2 ganz außen (und wird damit zeitlich am Ende ausgeführt, obwohl er in der Elm-Syntax am Anfang steht). Schauen wir uns wieder den Call-Stack an:

sumUpTo2 0 12000
sumUpTo2 12000 11999 -- hier wurde Zeile 142 aufgerufen
sumUpTo2 (12000 + 11999) 11998
sumUpTo2 23999 11998
sumUpTo2 (23999+11998) 11997
sumUpTo2 35997 11997

und in der Tat bleibt der Stack immer klein. Sie können nun riesige Zahlen eingeben:

sumUpTo2 0 1000000000                    
500000000995475700

Ich habe die Laufzeit mit Herrn Schellenbergers Modul gemessen. Auf meinem Rechner braucht es für \(n = 10^9\), also eine Milliarde, eine knappe Sekunde. Das ist nur etwas langsamer als mit Java (circa 0.7 Sekunden). Das Ergebnisse in Elm ist übrigens falsch. Richtig wäre 500000000500000000. Das liegt daran, dass Elm nach Javascript kompiliert und Javascript anscheinend hohe Integers in Float konvertiert, wodurch Rundungsfehler mit ins Spiel kommen. Ein Nachteil von sumUpTo2 ist, dass es zwei Parameter hat. Die Standardlösung ist, einen "Wrapper" zu schreiben, der dann sumUpTo2 0 n aufruft.

Jetzt sind Sie dran. Hier sehen Sie meinen Code für isPrime.

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

    else if modBy k n == 0 then
        True

    else
        hasDivisorLessThan (k - 1) n


isPrime : Int -> Bool
isPrime n =

    not (hasDivisorLessThan (n - 1) n)

Hier ist meine Funktion, die die Primzahlen von \(1\) bis \(n\) zählt:

countPrimesUntil : Int -> Int
countPrimesUntil n =
    if n <= 1 then
        0

    else
        let
            primesUntilNminus1 : Int
            primesUntilNminus1 =
                countPrimesUntil (n - 1)
        in
        if isPrime n then
            primesUntilNminus1 + 1

        else
            primesUntilNminus1

Dies ist nicht Endrekursion, und in der Tat gibt mir countPrimesUntil 10000 die bekannte Fehlermeldung.

List.length ( reverse (List.range 0 10000) )                            
10001