Rekursion Beispiele

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Die Fibonaccizahlen 1.1 iterativ 1.2 rekursiv 2 Fraktale 2.1 Quadratpflanze 2.2 Sierpinski-Dreieck 2.3 Koch-Schneeflocke 2.4 Hilbert - zum Weiterarbeiten 3 Musterlösungen 4 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.

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++) { ergebnis = f1 + f2; f1 = f2; f2 = ergebnis; } return f2; }

fibo_it(3);

ausführen

rekursiv

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

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

fibo_rek(4);

ausführen

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.

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);

ausführen

function pflanze(l,n){ if (n>1) { turtle.forward(l); turtle.left(90); pflanze(l/3,n-1); turtle.right(90); pflanze(l/3,n-1); turtle.right(90); pflanze(l/3,n-1); turtle.left(90); turtle.forward(l); } else turtle.forward(l); }

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 [1])

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);

ausführen

function sierpinski(l,t) { if (t>1) { sierpinski(l/2, t-1); turtle.forward(l/2); sierpinski(l/2, t-1); turtle.left(60); turtle.backward(l/2); turtle.right(60); sierpinski(l/2, t-1); turtle.right(60); turtle.backward(l/2); turtle.left(60); } else { turtle.forward(l); turtle.right(120); turtle.forward(l); turtle.right(120); turtle.forward(l); turtle.right(120); } }

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);

ausführen

function koch(l,t){ if (t>1) { koch(l/3, t-1); turtle.left(60); koch(l/3, t-1); turtle.right(120); koch(l/3, t-1); turtle.left(60); koch(l/3, t-1); } else turtle.forward(l); }

Hilbert - zum Weiterarbeiten

Beispiel in Logo hier: [[2]]

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

ausführen

Musterlösungen

Hier Musterlösungen zum Vervollständigen...

PWiki_Rekursion_Musterlösungen.pdf (0.5 MB)

Ackermann-Funktion

Informiere Dich zur Ackermann-Funktion unter [3]