Rekursionen

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Abgestützte Prozeduren

Wir wissen: Neue Objekte können mit bereits definierten Prozeduren beschrieben werden.

Beispiel: Volumen eines geraden Kreiszylinders:

Zylinder1.gif

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

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:

Binärbaum1.gif
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 Turtle-Grafik wollen wir eine gleichwertige Implementation vornehmen. Dazu definieren wir den Baum mit sich selbst.

Hinweis: Hier finden Sie die Sprachelemente der Turtle-Grafik.

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.

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\limits_{i=1}^{n}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:

Fakultät1.gif

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 [8], S. 42:

Affenmodell1.gif

"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

  1. Summe natürlicher Zahlen

    Ermitteln Sie die Summe einer beliebigen Anzahl natürlicher Zahlen: $S=\sum\limits_{i=0}^{n}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.

     

    Quelltext überprüfen:

  2. Summe ganzer Zahlen

    Schreiben Sie nun eine Prozedur summe-von-bis, die die Summe ganzer Zahlen in einem abgeschlossenen Intervall bildet.

     

    Quelltext überprüfen:

    Überprüfen Sie das Prozedurergebnis mit einer Hilfsprozedur, die eine Summenformel ganzer Zahlen nutzt (Herleitung!).

     

    Quelltext überprüfen:

  3. Vokalzähler

    In einer Zeichenkette sollen alle Vokale unabhängig von ihrer Groß- oder Kleinschreibung gezählt werden.
    Vervollständigen Sie die entsprechende Prozedur.

     

    Quelltext überprüfen:

  4. Teilzeichenketten

    In Datenbanksystemen gehört die Suche nach Teilen einer Zeichenkette zur Standardfunktionalität.
    Implementieren Sie das Prädikat (substring? <zk1> <zk2>), das entscheiden soll, ob die Zeichenkette zk1 in der Zeichenkette zk2 enthalten ist.

    Hinweis:

    Zum Vergleich von Zeichenketten wird der Vergleichsoperator equal? benötigt. Weitere Informationen zu Vergleichsoperatoren findet man hier.

     

    Quelltext überprüfen:

  5. Widerstandsnetzwerk

    Zunächst besteht eine einfache elektrische Grundschaltung aus 2 gleichgroßen Widerständen. Durch Anhängen weiterer dieser Grundschaltungen entsteht daraus ein komplexes Widerstandsnetzwerk:

    Widerstandsnetzwerk1.GIF


    Entwickeln Sie eine Prozedur, die den Gesamtwiderstand zwischen den Anschlussklemmen $A$ und $B$ berechnet, wenn $n$ Grundschaltungen zu diesem Widerstandsnetzwerk zusammengesetzt wurden.

     

    Quelltext überprüfen:

    ZA: Grenzwert des Gesamtwiderstandes

    Zeigen Sie, dass mit $n \rightarrow \infty$ für den Grenzwert des Gesamtwiderstandes dieses Widerstandsnetzwerkes gilt:

    $R_{Ges} = \frac{\sqrt{5}+1}{2} R$

    Überprüfen Sie die obige Widerstandsberechnung mit der Berechnung dieses Grenzwertes:

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, die Koch-Schneeflocke und die Peano-Kurve:

Sierpinski Koch Peano1.gif

Beschreiben Sie die drei Fraktale verbal und implementieren Sie diese mit der Turtle-Grafik.

Zur Problemlösung.

Persönliche Werkzeuge