Rekursionen
Inhaltsverzeichnis |
Abgestützte Prozeduren
Wir wissen: Neue Objekte können mit bereits definierten Prozeduren beschrieben werden.
Beispiel: Volumen eines geraden Kreiszylinders:
 |
|
Man sagt: Die Definition von zylindervolumen wird auf der Definition von kreisflaeche abgestützt.
Wie sinnvoll ist es, Prozeduren auf sich selbst abzustützen?
Selbstähnlichkeiten
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:
 |
|
Wir stellen fest, dass es durchaus sinnvoll sein kann, Objekte mit sich selbst zu beschreiben.
Mit der Turtle-Grafik wollen wir eine gleichwertige Implementation vornehmen. Dazu definieren wir den Baum mit sich selbst.
|
|
Prozeduren, die mit sich selbst definiert werden, heißen rekursive1) Prozeduren.
Rekursionen stellen ein leistungsstarkes und universelles Konzept zur Problemlösung dar.
1) recurrere (lat.): "zurücklaufen"
Rekursive Fakultätsfunktion
Nun analysieren wir die mathematische Definition der Fakultätsfunktion:
n!=\prod^n_{i=1}i=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}
Auch hier 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 bei WAGENKNECHT in [[Grundlagen der funktionsorientierten Programmierung mit SCHEME#Literatur|[8], 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."
Aufgaben
-
Summe natürlicher Zahlen
Ermitteln Sie die Summe einer beliebigen Anzahl natürlicher Zahlen: S=\sum^n_{i=0}i=1 + 2 + 3 + ... + n.
Im Gegensatz zu Carl Friedrich Gauß (* 30. April 1777; † 23. Februar 1855; deutscher Mathematiker, Astronom und Physiker) soll (noch) keine Summenformel benutzt werden!- Beschreiben Sie die rekursive Definition einer Summenfunktion.
- Skizzieren Sie das entsprechende Trichtermodell.
- Implementieren Sie die Summenfunktion summe als rekursive Prozedur.
-
Summe ganzer Zahlen
Schreiben Sie nun eine Prozedur summe-von-bis, die die Summe ganzer Zahlen in einem abgeschlossenen Intervall bildet.
Überprüfen Sie das Prozedurergebnis mit einer Hilfsprozedur, die eine "Summenformel ganzer Zahlen" nutzt (Herleitung!). -
Vokalzähler
In einer Zeichenkette sollen alle Vokale unabhängig von ihrer Groß- oder Kleinschreibung gezählt werden.
Vervollständigen Sie die entsprechende Prozedur.
Zum Weiterarbeiten
Fraktale
Mit selbstähnlichen Figuren bzw. Objekten beschäftigt sich heute ein ganzes Teilgebiet der Mathematik, die fraktale Geometrie. Ihre Untersuchungsergebnisse reichen in die Funktions- und Berechnbarkeitstheorie hinein und haben einen wesentlichen Einfluss auf die Chaosforschung komplexer dynamischer Systeme.
Klassische selbstähnliche oder fraktale Figuren sind das Sierpinski-Dreieck und die Koch-Schneeflocke:
Beschreiben Sie beide Fraktale verbal und implementieren Sie diese mit der Turtle-Grafik.
Zur Problemlösung.