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 Ackermann-Funktion

Die Fibonaccizahlen

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

Definition:

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

iterativ

Zunächst eine iterative Version:

function fibo_it(n:integer):integer;
var f1,f2,i:integer;
begin
  result := 1;
  f1 := 1;
  f2 := 1;
  for i := 3 to n do
  begin
   result := f1 + f2;
   f1 := f2;
   f2 := result;
  end;
end;

rekursiv

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

function fibo_rek(n:integer):integer; 
begin
//ergänzen (wieder in Lazarus-Syntax)
end;

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. 
Die Fraktale werden wieder mit der Turtle in JAVASCRIPT erstellt.

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

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: [[3]]

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 in Javascript

ausführen

Ackermann-Funktion

Informiere Dich zur Ackermann-Funktion unter [4]