Turtlegrafik (III)

Selbstähnlichkeiten

Der Binärbaum

Zunächst betrachten wir das nachfolgende Grafikobjekt, das wir als Binärbaum bezeichnen wollen. Dabei fällt auf, dass jeder Ast wieder ein kleiner Binärbaum ist.
Wir wollen diese Selbstähnlichkeit zu seiner Beschreibung ausnutzen:

Beschreibung: Der einfachste Binärbaum besteht aus einem Stamm. Jeder andere Binärbaum besteht aus einem Stamm sowie einem vereinfachten linken und einem vereinfachten rechten Binärbaum.

Wir stellen fest, dass es durchaus sinnvoll sein kann, Objekte mit sich selbst zu beschreiben.
Mit der Turtlegrafik wollen wir eine gleichwertige Implementation vornehmen. Dazu definieren wir den Baum mit sich selbst.

Prozeduren, die mit sich selbst definiert werden, heißen rekursive¹⁾ Prozeduren.
Rekursionen stellen ein leistungsstarkes und universelles Konzept zur Problemlösung dar.

¹⁾ recurrere (lat.): "zurücklaufen"

Die "Quadratschnecke"

Beschreibung:

• Die einfachste Quadratschnecke besteht aus einer Strecke.
• Jede andere Quadratschnecke besteht aus einer Strecke, einer Drehung um 90° sowie einer etwas verkürzten Quadratschnecke.

Ein Ausflug in die Mathematik: Rekursive Fakultätsfunktion

Nun analysieren wir die mathematische Definition der Fakultätsfunktion:

n!=1 \cdot 2 \cdot 3 \cdot ... \cdot n

bzw. rekursiv:

n!=\begin{cases}1,\mbox{wenn}\hspace{0.3em}n=0\\n \cdot (n-1)!\end{cases}

In der zweiten Beschreibung ist die Definition mit sich selbst offensichtlich.

Beschreibung:

• Die Fakultät einer Zahl ist 1, wenn die Zahl 0 ist,
• anderenfalls berechnet sie sich aus dem Produkt dieser Zahl mit der Fakultät ihres Vorgängers.

Implementation:

Beachte: Rekursive Prozeduren enthalten neben dem rekursiven Prozeduraufruf immer eine Elementarbedingung!

Das Affenmodell

Eine schöne Interpretation des rekursiven Prozeduraufrufes finden wir in dem Buch "Rekursionen - Ein didaktischer Zugang mit Funktionen" von Chr. Wagenknecht (Dümmler Verlag, Bonn 1994, S. 42):

"Der Auftrag, der von außen dem höchsten Oberaffen übergeben wurde, wird von diesem nicht vollständig bearbeitet, sondern in etwas abgeschwächter Form dem untergebenen Affen übergeben. Dieser verhält sich ebenso zu seinem Untergebenen. Der letzte Affe in dieser Hierarchie kann den ihm übergebenen Auftrag erfüllen und dem übergeordneten Affen übergeben. Jeder weitere Affe hat die Pflicht, das Resultat der Erledigung seines Auftrages seinem Auftraggeber zu übergeben. Schließlich kann der Ranghöchste sein Ergebnis abliefern.
Parallelen zu Einrichtungen, Ämtern und Institutionen unserer Gesellschaft sind unbeabsichtigt oder rein zufällig."