Übungen: Rekursive Datenstrukturen

Aufgabe 1: Liste als rekursive Datenstruktur

Tatsächlich stellen auch Listen nichts anderes als eine rekursive Datenstruktur dar. So können wir Listen 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

In dieser Aufgabe werden wir uns eine eigene Listendefinition in Racket implementieren. Das bedeutet: Alle Listenfunktionen wie cons, list, empty, first, rest usw. darfst du hier nicht nutzen!

(a) Schreibe eine Record-Definition für eine leere und eine nichtleere Liste von Zahlen.

(b) Erstelle mithilfe deiner Definitionen aus (a) eine Liste mit den Zahlen:  -4, -2, 0, 2, 4

(c) Schreibe eine Funktion, die die Länge deiner Liste bestimmt.

(d) Schreibe eine Funktion, die den Mittelwert deiner Liste berechnet.

Aufgabe 2: Sierpinski-Dreieck

Rekursive Datenstrukturen müssen nicht zwingend mithilfe von Records dargestellt werden. Wir können uns diese auch grafisch vorstellen. Eine solche Struktur stellt beispielsweise das Sierpinski-Dreieck dar, welches als Basisfall (Rekursionstiefe 0) ein einzelnes Dreieck darstellt und jedes nächste Dreieck optisch aus drei Dreiecken des Vorangegangenen besteht.

(a) Betrachte die drei Sierpinski-Dreiecke für unterschiedliche Rekursionstiefen. Überlege dir, wie man jeweils aus dem vorangegangenen das nachfolgende Dreieck darstellen kann.

(b) Die von uns genutzte Racket-Version bietet die Möglichkeit, geometrische Formen darzustellen. Teste hierzu die folgenden REPL-Eingaben:

> (triangle 60 "solid" "blue")

> (above (square 40 "outline" "red") (triangle 50 "solid" "blue"))

> (beside (square 40 "outline" "red") (triangle 50 "solid" "blue"))

(c) Stelle mithilfe der in (b) vorgestellten Funktionen die Formen von Rekursionstiefe 1 und 2 des Sierpinski-Dreiecks dar.

(d) Schreibe eine Funktion, die dir für die übergebene Rekursionstiefe das entsprechende Sierpinski-Dreieck darstellt.