i

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

  1. Erkläre die Berechnungsschritte.
  2. 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

Suche

v
8.2.2.10.2.1.3
inf-schule.de/deklarativ/fp_elm/elm_programme/rekursion/begruessungen/lernstrecke/aufwand
inf-schule.de/8.2.2.10.2.1.3
inf-schule.de/@/page/NYxVc51pa00Vds4U

Rückmeldung geben