Aufwandsbetrachtung

Den Rechen- und Verwaltungsaufwand analysieren

Wir betrachten die rekursive Funktionsdefinition aus dem letzten Abschnitt zusammen mit einem Funktionsaufruf.

anzahlWege n k =
    if (k == 0) || (k == n) then 
        1 
    else 
        (anzahlWege (n-1) (k-1)) + (anzahlWege (n-1) k)

> anzahlWege 5 2
10 : number

Wie wird ein solcher Funktionsaufruf ausgewertet? Die folgende Übersicht verdeutlicht die einzelnen Berechnungsschritte, die Elm bei dem vorgegebenen Funktionsaufruf ausführt.

anzahlWege 5 2 ->
(anzahlWege 4 1) + (anzahlWege 4 2) ->
((anzahlWege 3 0) + anzahlWege 3 1)) + (anzahlWege 4 2) ->
(1 + anzahlWege 3 1) + (anzahlWege 4 2) ->
(1 + ((anzahlWege 2 0) + (anzahlWege 2 1))) + (anzahlWege 4 2) ->
(1 + (1 + ((anzahlWege 1 0) + (anzahlWege 1 1)))) + (anzahlWege 4 2) ->
(1 + (1 + (1 + (anzahlWege 1 1)))) + (anzahlWege 4 2) ->
(1 + (1 + (1 + 1))) + (anzahlWege 4 2) ->
...

Aufgabe 1

(a) Erkläre die angegebenen Berechnungsschritte.

(b) Ergänze die noch fehlenden Berechnungsschritte.

(c) Begründe, warum das Berechnungsverfahren ineffizient ist.

Aufgabe 2 (für Experten)

Die Verarbeitungsschritte kann man mit der folgenden Funktion nachvollziehen. Erkläre wie das Ergebnis zustande kommt und wie es mit den oben gezeigten Berechnungsschritten zusammenhängt.

wege: Int -> Int -> String -> String
wege n k aufrufe =
    let
        aufrufeNeu = aufrufe ++ "|" ++ (String.fromInt n) ++ (String.fromInt k)
    in
    if (k == 0) || (k == n) then 
        aufrufeNeu 
    else 
        (wege (n-1) (k-1) aufrufeNeu) ++ (wege (n-1) k aufrufeNeu)

> wege 5 2 ""
"|52|41|30|52|41|31|20|52|41|31|21|10|52|41|31|21|11|52|42|31|20|52|42|31|21|10|52|42|31|21|11|52|42|32|21|10|52|42|32|21|11|52|42|32|22" : String