PMG1617/Rekursion Beispiele
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
=== Die Fibonaccizahlen ===
'''Leonardo Fibonacci di Pisa''' (* um 1180; † 1241) beschrieb die Fortpflanzung von Kaninchen mit der Zahlenfolge:
<blockquote><math>1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...</math></blockquote>
'''Definition:'''
<blockquote>
<math>\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}</math>
</blockquote>
'''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;
<code id="51ab9ee322d07" hidden>function fibo_rek(n:integer):integer;
begin
if (n=1) or (n=2) then result:=1
else result:= fibo_rek(n-1)+fibo_rek(n-2);
end;</code>
<language>Javascript</language>
== <font color=darkgreen size=4>''Fraktale''</font> ==
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.<br />
[[Bild:Mandelbrot1.png|miniatur|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:
<blockquote>[[Bild:Sierpinski_Koch1.GIF]]</blockquote>
Beschreibe beide ''Fraktale'' verbal.
'''Hinweis:''' Zur Implementation fraktaler Figuren stehen Dir die [[PMG/Kurs_11/Rekursion_I/Turtle_Sprachelemente|Sprachelemente der Turtle-Grafik]] zur Verfügung.
'''Die Fraktale werden wieder mit der Turtle in JAVASCRIPT erstellt.'''
<language>Javascript</language>
=== <font color=darkgreen size=4>''Quadratpflanze''</font> ===
Die Bilder zeigen die Entstehung einer Quadratpflanze.<br>
Bei jedem neuen Aufruf beträgt die Seitenlänge jeweils nur noch ein Drittel der vorherigen.<br>
[[Bild: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.<br>
<canvas w=800 h=500></canvas>
<run id="59dfc2c7839ab">
var c = new Canvas(1);
c.clear(); // Zeichenfläche löschen
var t = new Turtle(1); // neuer Turtle auf Zeichenfläche 1
t.move(400,400);
</run>
=== <font color=darkgreen size=4>''Sierpinski-Dreieck''</font> ===
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])
<blockquote>[[Bild: Sierpinski1.GIF]]</blockquote>
<code id="59dfc26726e7b" hidden>
procedure Sierpinski(l: real; t: Integer);
begin
if t > 1 then begin
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);
end
else
begin
turtle_forward(l);
turtle_right(120);
turtle_forward(l);
turtle_right(120);
turtle_forward(l);
turtle_right(120);
end;
end;
</code>
procedure Sierpinski(l: real; t: Integer);
begin
if t > 1 then begin
sierpinski(l/2, t-1);
turtle_forward(l/2);
//ergänzen
=== <font color=darkgreen size=4>''Koch-Schneeflocke''</font> ===
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:
<blockquote>[[Bild: Kochkurve1.GIF]]</blockquote>
analog zu obigem Beispiel selbstständig implementieren
<code id="59dfc26726eeb" hidden>
procedure flocke(l: real; t: Integer);
begin
if t > 1 then begin
flocke(l/3, t-1);
turtle_left(60);
flocke(l/3, t-1);
turtle_right(120);
flocke(l/3, t-1);
turtle_left(60);
flocke(l/3, t-1);
end
else
begin
turtle_forward(l);
end;
end;
procedure flocke_teil2(l: real; t: Integer);
begin
if t > 1 then begin
flocke_teil2(l/3, t-1);
turtle_left(60);
flocke_teil2(l/3, t-1);
turtle_right(120);
flocke_teil2(l/3, t-1);
turtle_left(60);
flocke_teil2(l/3, t-1);
end
else
begin
turtle_forward(l);
end;
end;
procedure flocke_teil3(l: real; t: Integer);
begin
if t > 1 then begin
flocke_teil3(l/3, t-1);
turtle_left(60);
flocke_teil3(l/3, t-1);
turtle_right(120);
flocke_teil3(l/3, t-1);
turtle_left(60);
flocke_teil3(l/3, t-1);
end
else
begin
turtle_forward(l);
end;
end;
</code>
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]