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
...