Fachkonzept: Rekursive Datenstrukturen
Rekursive Datenstrukturen
In vielen Fällen ist es wichtig, Beziehungen zwischen einzelnen Daten direkt innerhalb der Daten abbilden zu können. Hierfür kommen rekursive Datenstrukturen zum Einsatz.
Rekursive Datenstrukturen sind Datenstrukturen, die in ihrer Definition
auf sich selbst verweisen. Damit ermöglichen sie es, Beziehungen zwischen einzelnen Daten darzustellen.
Beispiel: Listenstruktur
Betrachtet man beispielsweise eine Listenstruktur, lässt sich diese wie folgt beschreiben:
- Eine Liste ist entweder:
- eine leere Liste
- oder eine nichtleere Liste
- Eine nichtleere Liste ist definiert durch:
- ein erstes Element
- und eine Liste als Rest
(define-record leereliste make-leereliste leereliste?) (define-record nichtleereliste make-nichtleereliste (nichtleereliste-element any) (nichtleereliste-nachfolgewert (mixed leereliste nichtleereliste)))
Die leere Liste stellt dabei den Basisfall der rekursiven Datenstruktur dar.
Ein Basisfall ist immer dann nötig, wenn es kein Element der rekursiven Datenstruktur gibt, auf welches verwiesen werden kann
(zum Beispiel beim letzten Element einer Liste).
Um darzustellen, dass eine Liste entweder leer
oder nichtleer ist, wird der Operator mixed genutzt, welcher beide
Möglichkeiten als valide Optionen zusammenführt.
