Rekursion Beispiele

Aus ProgrammingWiki
< PMG1617
Archivierte Version vom 2017-10-12T19:32:45+00:00. Aktuelle Version

Inhaltsverzeichnis

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: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.

Mandelbrot1.png
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:

Sierpinski_Koch1.GIF
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.


Thomas_Pflanze.JPG

  • 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.


Ihr Browser unterstützt Canvas nicht. 


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)
 Sierpinski1.GIF



procedure Sierpinski(l: real; t: Integer); 
begin 
if t > 1 then begin 
sierpinski(l/2, t-1);
turtle_forward(l/2);
//ergänzen

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:
 Kochkurve1.GIF



analog zu obigem Beispiel selbstständig implementieren


procedure flocke(l: real; t: Integer); 
begin 
if t > 1 then begin 
flocke(l/3, t-1);
turtle_left(60);
//ergänzen
Ackermann-Funktion

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