Fachkonzept - Endrekursion
Aufwand bei einer rekursiven Berechnung
Die Auswertung einer Ausdrucks mit rekursiven Funktionsdefinitionen ist mit einem hohen Verwaltungsaufwand verbunden. Oft kommt es - wie im folgenden Beispiel - vor, dass ein Funktionsaufruf einen neuen Funktionsaufruf erzeugt, bevor er endgültig ausgewertet werden kann. Das Ausführsystem muss dann nur teilweise ausgewertete Ausdrücke auf einem Stapel zwischenlagern, bevor die Auswertung endgültig abgeschlossen werden kann. Im vorliegenden Beispiel muss als letzte Operation immer noch eine Addition nach einem rekursiven Funktionsaufruf ausgeführt werden.
anzahlBegruessungen 6 -> (anzahlBegruessungen 5) + 5 -> ((anzahlBegruessungen 4) + 4) + 5 -> (((anzahlBegruessungen 3) + 3) + 4) + 5 -> ((((anzahlBegruessungen 2) + 2) + 3) + 4) + 5 -> (((((anzahlBegruessungen 1) + 1) + 2) + 3) + 4) + 5 -> ((((0 + 1) + 2) + 3) + 4) + 5 -> (((1 + 2) + 3) + 4) + 5 -> ((3 + 3) + 4) + 5 -> (6 + 4) + 5 -> 10 + 5 -> 15
Das kann zu Fehlermeldungen führen, wenn das Ausführsystem nicht mehr genügend Ressourcen für die Verwaltung zur Verfügung hat.
> anzahlBegruessungen 10000
49995000 : number
> anzahlBegruessungen 100000
RangeError: Maximum call stack size exceeded
Endrekursion als Ausweg
Einen hohen Verwaltungsaufwand kann man manchmal vermeiden, indem man rekursive Funktionsaufrufe geschickt ans Ende verlagert.
Die Funktion anzahlBegruessungen
lässt sich mit einer rekursiven Hilfsfunktion anzahlBegruessungenMitAkku
auch so definieren.
anzahlBegruessungenMitAkku: Int -> Int -> Int
anzahlBegruessungenMitAkku anzahlPersonen akku =
if anzahlPersonen == 1 then
akku
else
anzahlBegruessungenMitAkku (anzahlPersonen-1) (akku + (anzahlPersonen-1))
anzahlBegruessungen: Int -> Int
anzahlBegruessungen anzahlPersonen =
anzahlBegruessungenMitAkku anzahlPersonen 0
Die Idee dieser Implementierung besteht darin, den Parameter akku
zu verwenden, um das Endergebnis schrittweise aufzubauen.
Die Auswertung eines Funktionsaufrufs verläuft dann so:
anzahlBegruessungen 6 -> anzahlBegruessungenMitAkku 6 0 -> anzahlBegruessungenMitAkku 5 5 -> anzahlBegruessungenMitAkku 4 9 -> anzahlBegruessungenMitAkku 3 12 -> anzahlBegruessungenMitAkku 2 14 -> anzahlBegruessungenMitAkku 1 15 -> 15 15 15 15 15 15 15
Das Ergebnis steht beim letzten Funktionsaufruf bereits fest und muss nur noch "durchgereicht" werden. Wenn das Ausführsystem solche Durchreichsituationen erkennt, dann kann es sehr viel Verwaltungsaufwand bei der Auswertung einsparen.
Im vorliegenden Beispiel kann Elm auch Funktionsaufrufe mit großen Zahlen als Übergebewerte auswerten.
> anzahlBegruessungen 10
45 : number
> anzahlBegruessungen 100
4950 : number
> anzahlBegruessungen 1000
499500 : number
> anzahlBegruessungen 10000
49995000 : number
> anzahlBegruessungen 100000
...
Endrekursion ist ein Verfahren zur Optimierung von rekursiven Funktionsaufrufen. Es lässt sich anwenden, wenn als letzte Operation innerhalb einer rekursiven Funktionsdefinition die Funktion selbst aufgerufen wird.