Rekursionsformen in der Funktionalen Programmierung

Rekursionsformen in der Funktionalen Programmierung

updated by rck, 2004-05-30

Rekursionen gibt es in so ziemlich jeder Programmiersprache, die Unterprogrammaufrufe ermöglicht. Selbst ohne diese sind Rekursionen möglich.

In der funktionalen Programmierung lassen sich rekursive Aufrufe sehr gut analysieren. Nicht um sonst gilt sie als Lehrsprache.

1 | 2 | 3 | 4 | 5 | 6 | 7

Baumartige (kaskadenartige) Rekursion
Die vierte und letzte mikroskopische Struktur ist wieder ein Klassiker: Pro Zweig können mehrere rekursive Aufrufe nebeneinander vorkommen. Klassisches Beispiel wäre Quicksort, welches ein gern gezeigtes Beispiel für anschauliche funktionale Programmierung ist. Quicksort `1 qsort:: Ord a => [a] -> [a]` `2 qsort [] = []` `3 qsort (xs) = (qsort kleiner) ++ [x] ++ (qsort groesser)` `4 where kleiner = [y\|y <- xs, y<x]` `5 groesser = [y\|y <- xs, y>x]`

Baumartige (kaskadenartige) Rekursion

Die vierte und letzte mikroskopische Struktur ist wieder ein Klassiker: Pro Zweig können mehrere rekursive Aufrufe nebeneinander vorkommen.

Klassisches Beispiel wäre Quicksort, welches ein gern gezeigtes Beispiel für anschauliche funktionale Programmierung ist.

Quicksort

1 qsort:: Ord a => [a] -> [a]
2 qsort []     = []
3 qsort (xs) = (qsort kleiner) ++ [x] ++ (qsort groesser)
4                where kleiner  = [y|y <- xs, y<x]
5                      groesser = [y|y <- xs, y>x]

Beschreibung Quicksort
Zeile 1 Wir sehen hier eine Besonderheit. Der Datentyp "a" steht für beliebig. [a] heißt "Liste mit beliebigen Elementen". Und Ord "a =>" heißt zu guter Letzt: Uns ist nicht ganz egal, welche Datentypen wir bekommen. Sie sollen in einer Ordnungsrelation zueinander stehen. Zeile 2 die Rekursion ist zu Ende, wenn die übergebene Liste leer ist. Wir liefern in diesem Fall eben die leere Liste zurück. Zeile 3 die eigentliche Rekursion. Hier spielt Haskell seine Stärken aus, in einer üblichen Imperativen Programmiersprache wäre der Code bei weitem nicht so kompakt. Eine sortierte Liste besteht aus dem Anteil der Vorgänger des ausgewählten Elements "(qsort kleiner)" und dem Anteil der Nachfolger des ausgewählten Elements "(qsort groesser)". Zeilen 4-5 hier stellen wir uns die beiden Listen mit Werten kleiner x, respektive größer x zusammen. Das wäre grundsätzlich auch in einer Zeile vorstellbar, ist jedoch so übersichtlicher.

Beschreibung Quicksort

Zeile 1 Wir sehen hier eine Besonderheit. Der Datentyp "a" steht für beliebig. [a] heißt "Liste mit beliebigen Elementen". Und Ord "a =>" heißt zu guter Letzt: Uns ist nicht ganz egal, welche Datentypen wir bekommen. Sie sollen in einer Ordnungsrelation zueinander stehen.

Zeile 2 die Rekursion ist zu Ende, wenn die übergebene Liste leer ist. Wir liefern in diesem Fall eben die leere Liste zurück.

Zeile 3 die eigentliche Rekursion. Hier spielt Haskell seine Stärken aus, in einer üblichen Imperativen Programmiersprache wäre der Code bei weitem nicht so kompakt.

Eine sortierte Liste besteht aus dem Anteil der Vorgänger des ausgewählten Elements "(qsort kleiner)" und dem Anteil der Nachfolger des ausgewählten Elements "(qsort groesser)".

Zeilen 4-5 hier stellen wir uns die beiden Listen mit Werten kleiner x, respektive größer x zusammen. Das wäre grundsätzlich auch in einer Zeile vorstellbar, ist jedoch so übersichtlicher.

Binominal Koeffizienten
Noch ein zweites Beispiel: die Binominal-Koeffizienten ("n über k"). Wir erinnern uns an das Pascalsche Dreieck. binom `1 binom :: (Integer,Integer) -> Integer` `2 binom (n,k)` `3 \| k == 0 \|\| n == k = 1` `4 \| otherwise = binom (n-1,k-1) + binom (n-1,k)`