PMG2426 4/Iteration und Rekursion
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Javascript</language>
== Definitionen ==
'''Iteration'''
bezeichnet das wiederholte Durchlaufen von Anweisungen. Typischerweise wird dabei mitgezählt, wie oft die jeweilige Aktion erledigt wird. Wir kennen dafür z.B. die Sprachkonstrukte
''for'' und ''while''.
Bei einer '''Rekursion'''
erfolgt die Definition eines Problems, einer Funktion oder eines Verfahrens "durch sich selbst". Es handelt sich also wieder um eine Wiederholung, aber <u>ohne Schleife</u>!
Das Ergebnis eines Verfahrens für die Eingabe $x$ wird auf das Ergebnis des gleichen Verfahrens für eine Eingabe $y$ zurückgeführt, das Ergebnis des Verfahrens für die Eingabe $y$ wird
wiederum auf das Ergebnis des Verfahrens für eine Eingabe $z$ zurückgeführt, usw.<br>
'''<u>Dabei muss mindestens für einen Wert das Ergebnis des Verfahrens bekannt sein!</u>'''
== Erste Beispiele ==
=== Fakultät ===
==== iterativ ====
<code id="67442b00305fd">
function fakultaet(n) {
var ergebnis = 1;
for (var i=1;i<=n;i++) {
ergebnis = ergebnis * i;
}
return ergebnis;
}
</code>
<run id="67442b003077e">
fakultaet(7);
</run>
<u>Abarbeitung für n=4:</u>
<table width="20%" border="1" cellpadding="0" cellspacing="2">
<tr>
<td><b><p align="center">i</p></b></td>
<td><b><p align="center">Ergebnis</p></b></td>
</tr>
<tr>
<td><p align="center">1</p></td>
<td><p align="center">1</p></td>
</tr>
<tr>
<td><p align="center">2</p></td>
<td><p align="center">2</p></td>
</tr>
<tr>
<td><p align="center">3</p></td>
<td><p align="center">6</p></td>
</tr>
<tr>
<td><p align="center">4</p></td>
<td><p align="center">24</p></td>
</tr>
</table>
==== rekursiv ====
<code id="67442b0030652">
function fakultaet_rek(n) {
//ergänzen
}
</code>
<run id="67442b00307d4">
fakultaet_rek(4);
</run>
<u>Abarbeitung für n=4:</u>
Aufruf $fak$_$rek(4):=4*fak$_$rek(3)$;
danach "Abstieg in die Rekursionstiefe":
$fak$_$rek(4):=4*fak$_$rek(3)$;
$fak$>_$rek(3):=3*fak$_$rek(2)$;
$fak$_$rek(2):=2*fak$_$rek(1)$;
$fak$>_$rek(1):=1*fak$_$rek(0)$;
Für n=0 liefert das Verfahren den bekannten Wert 1.<br>
Der rekursive "Aufstieg" liefert dann:
$fak$_$rek(1):=1*1=1$;
$fak$_$rek(2):=2*1=2$;
$fak$_$rek(3):=3*2=6$;
$fak$_$rek(4):=4*6=24$;
===== Das Affenmodell =====
Eine schöne Interpretation des rekursiven Prozeduraufrufes finden wir bei W<small>AGENKNECHT</small> in: Rekursionen - Ein didaktischer Zugang mit Funktionen, Dümmler Verlag, Bonn 1994.
<blockquote>
[[Bild:Affenmodell1.gif]]
</blockquote>
''"Der Auftrag, der von außen dem höchsten Oberaffen übergeben wurde, wird von diesem nicht vollständig bearbeitet, sondern in etwas abgeschwächter Form dem untergebenen Affen übergeben. Dieser verhält sich ebenso zu seinem Untergebenen. Der letzte Affe in dieser Hierarchie kann den ihm übergebenen Auftrag erfüllen und dem übergeordneten Affen übergeben. Jeder weitere Affe hat die Pflicht, das Resultat der Erledigung seines Auftrages seinem Auftraggeber zu übergeben. Schließlich kann der Ranghöchste sein Ergebnis abliefern.<br /> Parallelen zu Einrichtungen, Ämtern und Institutionen unserer Gesellschaft sind unbeabsichtigt oder rein zufällig."''
=== Die Fibonaccizahlen ===
'''Leonardo Fibonacci di Pisa''' (* um 1180; † 1241) beschrieb die Fortpflanzung von Kaninchen mit der Zahlenfolge:
<blockquote>$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...$</blockquote>
'''Definition:'''
<blockquote>
$\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}$
</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.
==== iterativ ====
Zunächst eine iterative Variante:
<code id="67442b00306a4">
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;
}
</code>
<run id="67442b0030823">
fibo_it(3);
</run>
<u>Abarbeitung für n=5:</u>
<table width="20%" border="1" cellpadding="0" cellspacing="2">
<tr>
<td><b><p align="center">i</p></b></td>
<td><b><p align="center">Ergebnis</p></b></td>
<td><b><p align="center">f1 </p></b></td>
<td><b><p align="center">f2 </p></b></td>
</tr>
<tr>
<td><p align="center"><font color=white>-</font></p></td>
<td><p align="center"><font color=white>1</font></p></td>
<td><p align="center"><font color=white>1</font></p></td>
<td><p align="center"><font color=white>1</font></p></td>
</tr>
<tr>
<td><p align="center"><font color=white>3</font></p></td>
<td><p align="center"><font color=white>2</font></p></td>
<td><p align="center"><font color=white>1</font></p></td>
<td><p align="center"><font color=white>2</font></p></td>
</tr>
<tr>
<td><p align="center"><font color=white>4</font></p></td>
<td><p align="center"><font color=white>3</font></p></td>
<td><p align="center"><font color=white>2</font></p></td>
<td><p align="center"><font color=white>3</font></p></td>
</tr>
<tr>
<td><p align="center"><font color=white>5</font></p></td>
<td><p align="center"><font color=white>5</font></p></td>
<td><p align="center"><font color=white>3</font></p></td>
<td><p align="center"><font color=white>5</font></p></td>
</tr>
<tr>
<td><p align="center"><font color=white>hugo</font></p></td>
<td><p align="center"><font color=white>hugo</font></p></td>
<td><p align="center"><font color=white>hugo</font></p></td>
<td><p align="center"><font color=white>hugo</font></p></td>
</tr>
</table>
==== rekursiv ====
Implementieren Sie nun die rekursive Variante entsprechend obiger Definition:
<code id="67442b00306f9">
function fibo_rek(n){
//ergänzen
}
</code>
<run id="67442b003087c">
fibo_rek(4);
</run>
=== Turtle zeichnet rekursiv - Selbstähnlichkeit ===
Wir betrachten das nachfolgende Grafikobjekt, das wir als Binärbaum bezeichnen wollen. [[Bild:Baum_10.JPG|miniatur|Baum mit n=10]]
Dabei fällt auf, dass jeder Ast wieder ein kleiner Binärbaum ist.<br />
Wir wollen diese ''Selbstähnlichkeit'' zu seiner Beschreibung ausnutzen:<br />
<canvas w=800 h=500></canvas>
<run id="67442b00308cd">
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);
function baum(n){
if (n>1) { t.forward(n*10);
t.right(45);
baum(n-1);
t.left(90);
baum(n-1);
t.right(45);
t.backward(n*10);
}
else { t.forward(10);
t.backward(10);
}
}
baum(8);
</run>
'''Beschreibung:'''
* Der einfachste Binärbaum (Aufruf: baum(1)) besteht aus einem Stamm.
* Jeder andere Binärbaum besteht aus einem Stamm sowie einem vereinfachten linken und einem vereinfachten rechten Binärbaum.
Wir stellen fest, dass es durchaus sinnvoll sein kann, Objekte mit sich selbst zu beschreiben.<br />
Dazu definiert man den Baum ''mit sich selbst''.
Prozeduren, die mit sich selbst definiert werden, heißen ''rekursive''<sup>1)</sup> ''Prozeduren''.
Rekursionen stellen ein ''leistungsstarkes und universelles Konzept'' zur Problemlösung dar.<br />
<sup>1)</sup> recurrere (lat.): "zurücklaufen"
== Zusammenfassung ==
'''Rekursion bietet sich dann an, wenn man ein gestelltes Problem durch eine Funktion schrittweise in ein etwas einfacheres Problem umwandeln kann.'''
'''typischer Aufbau einer rekursiven Funktion'''
* 1. $if$-Befehl, der das Ende der Selbstaufrufe bestimmt
* 2. ein Aufruf der Funktion selbst
'''Nachteile der Rekursion'''
* 1. Jeder Aufruf kostet Zeit - Rekursion prinzipiell langsamer als Iteration
* 2. jeder Aufruf kostet Speicherplatz - viel Speicher im Stack (Speicherstapel)
Jede Iteration kann als Rekursion formuliert werden, jede Rekursion als Iteration (teilweise schwierig).
Rekursionen werden durch den Compiler bzw. Interpreter der Programmiersprache aufgelöst - der PC-Prozessor arbeitet iterativ.
== Rekursive Folgen ==
weitere Hilfen und Beispiele (incl. "Bewerbungstest"); [https://www.matheprisma.uni-wuppertal.de/Module/Rekurs/pages/node3.htm]