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.

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
...

Aufgabe 1

(a) Erläutere wie man von den Reduktionen zur rekursiven Funktionsdefinition gelangt.

(b) Teste die Funktionsdefinition in der REPL.

Aufgabe 2

Löse mit Hilfe der Funktion anzahlWege das Ausgangsproblem: Wie viele Wege gibt es vom Startpunkt (0,0) zum Zielpunkt (9,4)?