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

Zusammenfassung & Fazit
Rekursion ist zwar oft sehr elegant, jedoch nicht immer effizient. Je weniger rekursive Aufrufe, je weiter am Anfang unsere Rekursion in der Skala der mikroskopischen Strukturen steht, desto schneller wird sie ausgeführt. Eine baumartige Struktur ist am ungünstigsten, gefolgt von der ebenfalls ungünstigen geschachtelten Rekursion. Soweit möglich, ist die schlichte Rekursion zu bevorzugen. Wenn man sich die Rekursion graphisch für ein kleines n vor Augen führt, wird man schnell feststellen, woran das liegt.

Zusammenfassung & Fazit

Rekursion ist zwar oft sehr elegant, jedoch nicht immer effizient. Je weniger rekursive Aufrufe, je weiter am Anfang unsere Rekursion in der Skala der mikroskopischen Strukturen steht, desto schneller wird sie ausgeführt.

Eine baumartige Struktur ist am ungünstigsten, gefolgt von der ebenfalls ungünstigen geschachtelten Rekursion. Soweit möglich, ist die schlichte Rekursion zu bevorzugen.

Wenn man sich die Rekursion graphisch für ein kleines n vor Augen führt, wird man schnell feststellen, woran das liegt.

Fazit
Rekursionen gibt's überall. Möchte man Laufzeiten analysieren oder generell das Verhalten von rekursiven Funktionen studieren, sind funktionale Programmiersprachen oft das Mittel der Wahl. Wer jedoch immer nur mit Datenbanken arbeitet und eher Komponenten zusammenstellt als selber Algorithmen ausprogrammiert, wird mit Rekursionen nicht besonders häufig in Berührung kommen.

Referenz
Haskell in der Schule: Sortierverfahren Sehr nette Auflistung diverser Sortierverfahren & deren Umsetzung in Haskell. 433 Beispiele in 132 Programmiersprachen Eine umfangreiche Seite, welche diverse Standardprogramme ("hello world", "fakultät", usw.) in verschiedensten Programmiersprachen vorstellt. Haskell ist gleich mit 13 Beispielen vertreten, auch LISP und selbst LOGO finden sich unter den Sprachen. LVA: Funktionale Programmierung mit Folien & Übungsbeispielen zur Vorlesung

Referenz

Haskell in der Schule: Sortierverfahren

Sehr nette Auflistung diverser Sortierverfahren & deren Umsetzung in Haskell.

433 Beispiele in 132 Programmiersprachen

Eine umfangreiche Seite, welche diverse Standardprogramme ("hello world", "fakultät", usw.) in verschiedensten Programmiersprachen vorstellt. Haskell ist gleich mit 13 Beispielen vertreten, auch LISP und selbst LOGO finden sich unter den Sprachen.

LVA: Funktionale Programmierung

mit Folien & Übungsbeispielen zur Vorlesung

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

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