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

Die lineare Rekursion
...ist unsere zweite mikroskopische Struktur, wir lernen noch zwei weitere kennen. Es findet sich in jedem Zweig wieder höchstens ein rekursiver Aufruf, dieser ist jedoch nicht notwendigerweise äußerste Operation. Somit ist die schlichte Rekursion ein Spezialfall der linearen Rekursion. Beispiel `1 powerThree :: Integer -> Integer` `2 powerThree n` `3 \| n == 0 = 1` `4 \| n > 0 = 3 * powerThree (n-1)`

Die lineare Rekursion

...ist unsere zweite mikroskopische Struktur, wir lernen noch zwei weitere kennen.

Es findet sich in jedem Zweig wieder höchstens ein rekursiver Aufruf, dieser ist jedoch nicht notwendigerweise äußerste Operation. Somit ist die schlichte Rekursion ein Spezialfall der linearen Rekursion.

Beispiel

1 powerThree :: Integer -> Integer
2 powerThree n
3 | n == 0 = 1
4 | n > 0 = 3 * powerThree (n-1)

Beschreibung powerThree
Sieht im ersten Moment strukturell wie das Beispiel zum größten gemeinsamen Teiler aus. Jedoch sticht ein Detail in Zeile 4 hervor. Der rekursive Aufruf steht nicht mehr alleine, sondern wird von einer Multiplikations-Operation begleitet.