Aufwandsbetrachtung
Den Rechen- und Verwaltungsaufwand analysieren
Wir betrachten die rekursive Funktionsdefinition aus dem letzten Abschnitt zusammen mit einem Funktionsaufruf.
anzahlBegruessungen : Int -> Int
anzahlBegruessungen anzahlPersonen =
if anzahlPersonen == 1 then
0
else
anzahlBegruessungen (anzahlPersonen - 1) + anzahlPersonen - 1
> anzahlBegruessungen 6
15 : number
Wie wird ein solcher Funktionsaufruf ausgewertet? Die folgende Übersicht verdeutlicht die einzelnen Berechnungsschritte, die Elm bei dem vorgegebenen Funktionsaufruf ausführt.
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
Aufgabe 1
- Erkläre die Berechnungsschritte.
- Erläutere anhand der Berechnungsschritte, dass bei einer rekursiven Funktionsdefinition immer wieder Funktionsaufrufe gewissermaßen auf einem Stapel abgelegt werden, bevor die Auswertung endgültig abgeschlossen werden kann. Die Auswertung eines Funktionsaufrufs bei einer rekursiven Funktionsdefinition ist demnach mit hohem Verwaltungsaufwand verbunden.
Aufgabe 2
Den hohen Verwaltungsaufwand kann man auch experimentell erkunden, indem man die Funktion mit immer größeren Zahlen aufruft.
Deute die Fehlermeldung, die man dabei irgendwann erhält.
> anzahlBegruessungen 10
45 : number
> anzahlBegruessungen 100
4950 : number
> anzahlBegruessungen 1000
499500 : number
> anzahlBegruessungen 10000
49995000 : number
> anzahlBegruessungen 100000
RangeError: Maximum call stack size exceeded
