Aufwandsbetrachtung

Den Rechen- und Verwaltungsaufwand analysieren

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

anzahlWege : Int -> Int -> Int
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 + 1))) + (anzahlWege 4 2) ->
...

Aufgabe 1

Aufgabe 2 (für Experten)

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