PMG1617/Rekursion Beispiele
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Javascript</language>
=== 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;
== <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.'''
=== <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="59dfc991628c3">
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);
</run>
<code id="59dfcbf8ec7af" hidden>
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);
}
</code>
=== <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>
<canvas w=800 h=500></canvas>
<run id="59dfc9916295c">
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);
</run>
<code id="59dfcbf8ec829" hidden>
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);
}
}
</code>
=== <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>
<canvas w=800 h=500></canvas>
<run id="59dfc991629d4">
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);
</run>
<code hidden>
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);
}
</code>
== Ackermann-Funktion ==
Informiere Dich zur Ackermann-Funktion unter [http://de.wikipedia.org/wiki/Ackermannfunktion]