Rekursive Funktion
Eine Funktionsdefinition entwickeln
Wir gehen von den Reduktionsschritten aus, die im letzten Abschnitt entwickelt wurden.
Rekursionsanfang bzw. Rückführungsanfang:
Falls k == 0:
anzahlWege n k -> 1
Falls k == n:
anzahlWege n k -> 1
Rekursionsschritt bzw. Rückführungsschritt:
Falls k > 0 und k < n:
anzahlWege n k -> anzahlwege (n - 1) (k - 1) + anzahlWege (n - 1) k
Wir nutzen diese Reduktionen zur Implementierung der Funktion anzahlWege
,
die folgende Struktur hat:
anzahlWege : Int -> Int -> Int
anzahlWege n k =
if ??? then
1
else
anzahlWege ???
> anzahlWege 5 2
...
Aufgabe 1
- Erläutere wie man von den Reduktionen zur rekursiven Funktionsdefinition gelangt.
-
Implementiere die Funktion
anzahlWege
in Elm und teste sie u.a. mit dem AufrufanzahlWege 5 2
.
Aufgabe 2
Löse mit Hilfe der Funktion anzahlWege
das Ausgangsproblem:
Wie viele Wege gibt es vom Startpunkt (0,0) zum Zielpunkt (9,4)?