PMG/Kurs 11/Iteration Rekursion

Wiki-Quelltext dieser Seite.

<language>Pascal</language>
== Definition ==


'''Iteration''' bezeichnet das wiederholte Durchlaufen von Anweisungen. Typischerweise wird dabei mitgezählt, wie oft die jeweilige Aktion erledigt wird. Wir kennen dafür die Sprachkonstrukte ''for..to..do, while..do, repeat..until''.

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 <math>x</math> wird auf das Ergebnis des gleichen Verfahrens für eine Eingabe <math>y</math> zurückgeführt, das Ergebnis des Verfahrens für die Eingabe <math>y</math> wird wiederum auf das Ergebnis des Verfahrens für eine Eingabe <math>z</math> zurückgeführt, usw.<br>
'''<u>Dabei muss mindestens für einen Wert das Ergebnis des Verfahrens bekannt sein!</u>'''


== Typische Beispiele ==


=== Fakultät ===

==== iterativ ====

<code id="4fd4ed668bafa">
function fak_it(n:integer):integer;
var ergebnis:integer;
begin
ergebnis:=1;
while n>1 do begin
             ergebnis:=n*ergebnis;
             n:=n-1;
             end;
result:=ergebnis;
end;
</code>

<run id="4fd4ed668bce7">
writeln(fak_it(3));
</run>

Abarbeitung für n=4:

 <table width="20%" border="1" cellpadding="0" cellspacing="2">
 <tr>
  <td><b><p align="center">n</p></b></td>
  <td><b><p align="center">Ergebnis</p></b></td>
 </tr>
 <tr>
  <td><p align="center">-</p></td>
  <td><p align="center">1</p></td>
 </tr>
 <tr>
  <td><p align="center">4</p></td>
  <td><p align="center">4</p></td>
 </tr>
 <tr>
  <td><p align="center">3</p></td>
  <td><p align="center">12</p></td>
 </tr>
 <tr>
  <td><p align="center">2</p></td>
  <td><p align="center">24</p></td>
 </tr>
 <tr>
  <td><p align="center">1</p></td>
  <td><p align="center">24</p></td>
 </tr>
</table>

==== rekursiv ====

<code id="4fd4ed668bb6e">
function fak_rek(n:integer):integer;

</code>

<run id="4fd4ed668bd53">
writeln(fak_rek(3));
</run>

Abarbeitung für n=4:

Aufruf <math>fak</math>_<math>rek(4):=4*fak</math>_<math>rek(3)</math>;

danach "Abstieg in die Rekursionstiefe": 

      <math>fak</math>_<math>rek(4):=4*fak</math>_<math>rek(3)</math>; 
          <math>fak</math>_<math>rek(3):=3*fak</math>_<math>rek(2)</math>;
              <math>fak</math>_<math>rek(2):=2*fak</math>_<math>rek(1)</math>;
                 <math>fak</math>_<math>rek(1):=1*fak</math>_<math>rek(0)</math>;

Für n=0 liefert das Verfahren den bekannten Wert 1.<br>
Der rekursive "Aufstieg" liefert dann: 
                <math>fak</math>_<math>rek(1):=1*1=1</math>;
                <math>fak</math>_<math>rek(2):=2*1=2</math>;
                <math>fak</math>_<math>rek(3):=3*2=6</math>;
                <math>fak</math>_<math>rek(4):=4*6=24</math>;

=== Potenz ===

Das Potenzieren wird bekanntermaßen iterativ z.B. so implementiert:

==== iterativ ====

<code id="4fd4ed668bbd8">
function pot(a,b:integer):integer;
var i,d: integer;
begin 
d:=1; 
for i:=1 to b do d:=d*a;
result:=d;
end;
</code>


<run id="4fd4ed668bdbb">
writeln(pot(4,2));
</run>

==== rekursiv ====

Vervollständigen Sie den Quelltext für die rekursive Berechnung einer Potenz!

<code id="4fd4ed668bc54">
function pot_rek(a,b:integer):integer; 
begin
 result := 0; // hier fehlt noch etwas
end;
</code>


<run id="4fd4ed668be24">
writeln (pot_rek(5,3));
</run>


== Turtle ==


<code id="4fd6546ff1522">
var isUp:Boolean;
    i:integer;
</code>

<run id="4fd6546ff15ce">
selectCanvas(1);
canvas_clear(); // Zeichenfläche löschen
turtle_move(200,100); // Turtle in die Mitte stellen

isUp := false;

for i := 0 to 17 do begin
 turtle_penColor(i*10+50,0,250-10*i);  
 turtle_penWidth(10);
 turtle_forward(20);  
 turtle_right(20); 
 isUp := not isUp; 
 if isUp then turtle_penUp() else turtle_penDown();
end;
</run>

<canvas w=400></canvas>



== 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. <math>if</math>-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.