Rekursion Beispiele

Aus ProgrammingWiki

< PMG1719

Archivierte Version vom 2018-08-16T11:02:01+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Die Fibonaccizahlen
- 1.1 iterativ
- 1.2 rekursiv
2 ''Fraktale''
3 Ackermann-Funktion

Die Fibonaccizahlen

Leonardo Fibonacci di Pisa (* um 1180; † 1241) beschrieb die Fortpflanzung von Kaninchen mit der Zahlenfolge:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Definition:

\mbox{fib}(n)=\begin{cases}1,\mbox{wenn}\hspace{0.3em}n=1\\1,\mbox{wenn}\hspace{0.3em}n=2\\\mbox{fib}(n-1)+\mbox{fib}(n-2),\mbox{sonst}\end{cases}

Beschreibung:

Die Kaninchenpaar bekommt nach zwei Monaten Nachwuchs (Pärchen!), dies dann jeden Monat. Die "Kinderpaare" verhalten sich genauso. Die Kaninchen leben "unendlich lange".

Das bedeutet:

Die ersten beiden Glieder der Zahlenfolge sind jeweils 1.
Jedes weitere Glied ergibt sich aus der Summe seiner beiden Vorgänger.

Prüfen!

siehe auch http://www.ijon.de/mathe/fibonacci/index.html

iterativ

Zunächst eine iterative Version:

function fibo_it(n){
   var ergebnis = 1;
   var f1 = 1;
   var f2 = 1;
   for (var i=3;i<=n;i++) {   
    ergenis = f1 + f2;
    f1 = f2;
    f2 = ergebnis;
   }
   return f2;
}

fibo_it(3);

rekursiv

Schreiben Sie nun eine rekursive Funktion gemäß der oberen Beschreibung:

function fibo_rek(n){ 
 
 //ergänzen
 
 }

fibo_rek(4);

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.

Die vielleicht berühmteste fraktale Struktur: Das Apfelmännchen

Der Begriff Fraktal (lat. fractus "gebrochen") geht auf den französisch-US-amerikanischen Mathematiker Benoît Mandelbrot (* 20. November 1924; † 14. Oktober 2010) zurück. Mit ihm werden natürliche oder künstliche Gebilde bzw. geometrische Muster bezeichnet, die einen hohen Grad an Selbstähnlichkeiten aufweisen.

Klassische selbstähnliche oder fraktale Figuren sind das Sierpinski-Dreieck und die Koch-Schneeflocke:

Beschreibe beide Fraktale verbal.

Hinweis: Zur Implementation fraktaler Figuren stehen Dir die Sprachelemente der Turtle-Grafik zur Verfügung.

Quadratpflanze

Die Bilder zeigen die Entstehung einer Quadratpflanze.
Bei jedem neuen Aufruf beträgt die Seitenlänge jeweils nur noch ein Drittel der vorherigen.

Finde in der "Quadratpflanze" die einfachere in der komplizierteren wieder.
- Formuliere also die "grundlegenden Gedanken" für das Zeichnen der Pflanze.
- Nach welcher Rekursionsvorschrift werden "Quadratpflanzen" erzeugt?
Zeichne den nächsten (vierten) Schritt in der Entwicklung.
Analog zum Baum soll eine "Quadratpflanze" mit der Turtle gezeichnet werden.

var c = new Canvas(1);
c.clear(); // Zeichenfläche löschen

var turtle = new Turtle(1); // neuer Turtle auf Zeichenfläche 1

turtle.move(100,400);
turtle.right(90);

function pflanze(l,n) {
if (n>1){   turtle.forward(l);
            turtle.left(90);
            pflanze(l/3,n-1);
//ergänzen

}
}
pflanze(200,3);

Sierpinski-Dreieck

Diese selbstähnliche Figur ist nach dem polnischen Mathematiker Wacław Franciszek Sierpiński (* 14. März 1882; † 21. Oktober 1969) benannt. Die nachfolgende Abbildung zeigt die Konstruktion dieses Dreiecks: (interessantes zur Anwendung auch unter http://en.wikipedia.org/wiki/Sierpinski_triangle)

var c = new Canvas(2);
c.clear(); // Zeichenfläche löschen

var turtle = new Turtle(2); // neuer Turtle auf Zeichenfläche 2

turtle.move(300,350);

function sierpinski(l,t) {
if (t>1){   sierpinski(l/2, t-1);
            turtle.forward(l/2);
            sierpinski(l/2, t-1);
            turtle.left(60);
            
//ergänzen

}
}

sierpinski(300,5);

Koch-Schneeflocke

Der schwedische Mathematiker Helge von Koch (* 25. Januar 1870; † 11. März 1924) stellte im Jahr 1904 einen stetigen Graphen vor, der an keiner Stelle differenzierbar ist. Die sogenannte Koch-Schneeflocke setzt sich aus drei dieser Koch-Kurven zusammen, die auf den Seiten eines gleichseitigen Dreiecks angeordnet sind:

var c = new Canvas(3);
c.clear(); // Zeichenfläche löschen

var turtle = new Turtle(3); // neuer Turtle auf Zeichenfläche 3

turtle.move(300,350);

function koch(l,t) {
if (t>1){   koch(l/3,t-1);
            turtle.left(60);
//ergänzen

}
}

koch(300,3);
turtle.right(120);
koch(300,3);
turtle.right(120);
koch(300,3);
turtle.right(120);

Hilbert - zum Weiterarbeiten

Beispiel in Logo hier: http://programmingwiki.de/Logo Hilbert

Informationen hier

var c = new Canvas(4);
c.clear(); // Zeichenfläche löschen

var turtle = new Turtle(4); // neuer Turtle auf Zeichenfläche 4

turtle.move(300,350);

// eigener Versuch

Ackermann-Funktion

Informiere Dich zur Ackermann-Funktion unter http://de.wikipedia.org/wiki/Ackermannfunktion

Rekursion Beispiele

Inhaltsverzeichnis

Die Fibonaccizahlen

iterativ

rekursiv

Fraktale

Quadratpflanze

Sierpinski-Dreieck

Koch-Schneeflocke

Hilbert - zum Weiterarbeiten

Ackermann-Funktion

Suche