Rekursionsformen in der Funktionalen Programmierung

Choose

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

Makroskopische Strukturen
Was wir bis jetzt gesehen haben, waren durchwegs direkte Rekursionen. Davon abgesehen gibt es aber auch noch die indirekte, auch als verschränkte (wechselweise) bekannte Rekursion. Beispiel verschränkte Rekursion `1 isEven :: Integer -> Bool` `2 isEven n` `3 \| n == 0 = True` `4 \| n > 0 = isOdd (n-1)` `5` `6` `7 isOdd :: Integer -> Bool` `8 isOdd n` `9 \| n == 0 = False` `10 \| n > 0 = isEven (n-1)`

Makroskopische Strukturen

Was wir bis jetzt gesehen haben, waren durchwegs direkte Rekursionen. Davon abgesehen gibt es aber auch noch die indirekte, auch als verschränkte (wechselweise) bekannte Rekursion.

Beispiel verschränkte Rekursion

1 isEven :: Integer -> Bool
2 isEven n
3   | n == 0      = True
4   | n >  0      = isOdd (n-1)
5
6
7 isOdd  :: Integer -> Bool
8 isOdd n
9   | n == 0      = False
10   | n >  0      = isEven (n-1)

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

Klassifikation
Die repetive (schlichte) Rekursion
Die lineare Rekursion
Geschachtelte Rekursion
Baumartige (kaskadenartige) Rekursion
Makroskopische Strukturen
Zusammenfassung & Fazit