und lokalen Variablen angelegt (gestapelt) • Die ... fileLászló Böszörményi ESOP Rekursive Algorithmen - 3 Ablauf der Fakultätsfunktion public class Faculty { // 18.09.2000

László Böszörményi ESOP Rekursive Algorithmen - 1

• Die Aufrufkette von Methoden bildet einen Kreis– Direkte Rekursion

• Methode ruft sich selber an: P → P

– Indirekte Rekursion• Methode wird indirekt „zurückgerufen“: P → Q, Q → R, R → P• „Länge“ des Kreises > 1

• Bei jedem Aufruf wird eine neue Instanz von Parametern und lokalen Variablen angelegt (gestapelt)

• Ähnliche Regeln wie bei rekursiven Definitionen1. Eine rekursive Prozedur muss einen nicht rekursiven Teil

haben (Trivialfall)2. Die Rekursion muss enden – zum Trivialfall führen


Fakultätsfunktion• Nicht-rekursive Definition (n! = 1 * 2 * . . . n)

– 0! = 1, n! = Πni = 1i, für n ≥ 1

• Nicht-rekursive Implementierungint Faculty (int n) { // Berechnet die Fakultätsfunktion für n ≥ 0

int f = 1; // f wird auf 1 initialisiertfor (int i = 1; i <= n; i++) f = f * i; // f = 1 * 2 * 3 * . . . * nreturn f;

} // Faculty• Rekursive Definition

– 0! = 1, n! = n (n –1)! für n ≥ 1• Rekursive Implementierung

int Faculty (int n) { // Berechnet die Fakultätsfunktion für n ≥ 0if (n == 0 ) return 1; // Trivialfallelse return n * Faculty (n - 1); // Rekursiver Aufruf:

} // Faculty // Führt zum Trivialfall (n = 0) 7206120524463221110fn


Ablauf der Fakultätsfunktionpublic class Faculty { // 18.09.2000. LB

static int GetPosInt() { . . . } // GetPosInt;

static int Faculty (int n) {if (n == 0 ) return 1;else return n * Faculty (n - 1);

} // Faculty

static void main(String [] args) {int N;Out.println("Fakultaetsfunktion");N = GetPosInt (); // Eingabe: 6Out.println("Fakultaet von " + N + ": "

+ Faculty(N));} // main

} // FacultyFakultaet von 6: 720

main 720

Fac(6) 6 * 120

Fac(5) 5 * 24

Fac(4) 4 * 6

Fac(3) 3 * 2

Fac(2) 2 * 1

Fac(1) 1 * 1

Fac(0) 1


Zahlenreihe umdrehenpublic class Reverse {

static int GetInt() { . . .} // GetInt

static void Reverse () {int i; // Bei jedem Aufruf von Reverse, neue Instanz von ii = GetInt(); // Liest nächste Zahl von der Tastaturif (i != 0) { // Bei Eingabewert == 0: Ende

Reverse(); // Nächster Aufruf: Stack wächstOut.println(i);

} // if} // Reverse

static void main(String [] args) {Out.println("Zahlenreihe umdrehen, endet mit 0");Reverse();

} // main} // Reverse

Eingabe: 2 4 6 8 10 0

Ausgabe: 10 8 6 4 2

i1 == 2i2 == 4i3 == 6i4 == 8Top of Stack nach

dem 4. Aufruf

Zu dem Punkt kommt die Ausführung erst beim „Aufstieg“ aus dem Trivialfall


Fibonacci Zahlen• Fib(0) = 1, Fib(1) = 1, Fib(n) = Fib(n-1) + Fib(n-2)• Implementierung:

static int Fib (int n) {if ( n <= 1) return 1; // n == 0 ∨ n == 1else return Fib(n - 1) + Fib(n - 2);

} // Fib• Ineffizient: Fib(5)

Fib(4)

Fib(3) Fib(2)

Fib(2) Fib(1)

Fib(1) Fib(0)

Fib(1) Fib(0)

Fib(3)

Fib(2) Fib(1)

Fib(1) Fib(0)2

3 2

5

8

2

3

217136855433221110Fn


• Rekursive Probleme1. Der Problembereich lässt sich in immer kleinere Teilprobleme

aufspalten, bis sie trivial werden (divide et impera)2. Bearbeitung rekursiver Datenstrukturen (siehe Kapitel 9)

• Finden von rekursiven Lösungen1. Suche den rekursiven Fall (der sich teilen lässt)2. Definiere die Endbedingung3. Prüfe Konvergenz

Gegenbeispiel:static int Wrong (int n) { // Fehlerhafte rekursive Prozedur

if (n == 1) return 1; // Falsche Endbedingung!else return n + Wrong(n - 2); // n + (n-2) + (n-4) + (n-6) + . . .

} // WrongHält nicht beim Aufruf mit geraden Zahlen


QuickSort (C.A.R. Hoare)1. Nehme aus dem Array ein beliebiges Element x2. Partitioniere es so, dass alle Elemente in der linken Hälfte ≤ x,

die in der Rechten ≥ x sind (vertausche die, die falsch stehen)3. Wende obigen Algorithmus rekursiv auf die linke bzw. rechte

Hälfte an, bis das Array trivial wird (enthält nur 1 Element)static void QuickSort (int [] a, int left, int right) { //Sortiert a

int i= left, j = right, x = a[(left + right) / 2], w; // x: mittleres Elementdo { while (a[i] < x) i++; // Suche Elemente,

while (a[j] > x) j--; // die zum tauschen sindif (i <= j) { // i > j: nichts zu tun

w = a[i]; a[i] = a[j]; a[j] = w; // Tauschi++; j--;

} // if i <= j} while (i <= j); // i > j: Ende der Partitionierungif (left < j) QuickSort (a, left, j);if (i < right) QuickSort (a, i, right);

} // QuickSort

Partitio-nierung

Rekur-sion

16 5 3 8 9 1 25 44 5 3 1 9 8 25 16 4 1 3 5 9 8 25 16 1 4 3 5 9 8 25 16 1 3 4 5 9 8 25 161 3 4 5 8 9 25 161 3 4 5 8 9 16 25 1 3 4 5 8 9 16 25

a0 a1 a2 a3 a4 a5 a6 a7


Die Türme von Hanoi• Drei Türme (Pfosten): Start, Finish und Temp• Auf Start liegen H Scheiben, der Größe nach sortiert, die

Größte ist unten• Wir müssen die Scheiben auf Finish transferieren so, dass

sie dort genauso geordnet sind• Wir dürfen immer nur eine Scheibe bewegen, und eine

größere darf nie auf einer kleineren liegen• Als Hilfe können wir den Pfosten Temp benutzen • Rekursive Lösung

– H = 0: nichts zu machen: Trivialfall– H > 0, wende die folgenden Regeln rekursiv an:

1. Turm der Höhe H – 1 von Start nach Temp bewegen (mittels Finish)2. Unterste Scheibe (eine Turm, mit Höhe = 1) von Start nach Finish

legen – die liegt nun richtig3. Turm der Höhe H – 1 von Temp nach Finish bewegen (mittels Start)


Türme von Hanoi – Datenstrukturenpublic class Hanoi { // Die Tuerme von Hanoi, 21.10.2000. LB

static final int Start = 0, Finish = 1, Temp= 2; // 3 Pfostenint H; // Höhe der Pfostenclass State{ // Zustand eines Pfostens

int top = 0; // Oberste Scheibenpositionint [] disks; // Scheiben-Nummer: 1 .. H, 0 für keine ScheibeState() {

disks = new int [H + 1]; // Scheiben: 1 .. H (statt 0 .. H-1 – bequemer)for (int j = 1; j <= H; j++) disks[j] = 0; // disks[0] unbenutzt

} // State} // StateState[] posts= new State [3]; // 3 Pfosten: Start, Finish, TempHanoi (int Hoehe) {

H = Hoehe;for (int i = 0; i < posts.length; i++) posts[i] = new State();posts[Start].top = H; // Start-Pfosten am Anfang: H Scheibenfor (int i = 1; i <= H; i++) posts[Start].disks[i] = H - (i - 1); // Position-1: Scheibe-H

} // Hanoi Position-H: Scheibe-1


Türme von Hanoi – Graphische Darstellungvoid line (int num, char muster) { // Schreibt muster num-mal aus

while (num > 0) { Out.print(muster); num--; } } // line void disk (int d) { // Darstellung einer Scheibe

if (d == 0) { // Die "leere" Scheibe"line (H, ' '); line (1, '|'); line (H, ' '); }

else { // Darstellung der Scheibe-dline (H - d, ' '); line (3 + 2*(d - 1), '='); line (H - d, ' '); } // if d

} // diskvoid display () {

for (int p = 0; p < posts.length; p++) disk(0); // Oben nur „nackte“ PfostenOut.println();for (int line = H; line > 0; line--) { // Von Oben gezeichnet

for (int p = 0; p < posts.length; p++) disk(posts[p].disks[line]);Out.println();

} // for lineOut.println();

} // display


Türme von Hanoi – Rekursive Lösungvoid transfer (int from, int to) { // Bewege eine Scheibe vom Pfosten to nach from

posts[to].top++; // Nächste leere Position am Pfosten toposts[to].disks[posts[to].top] = posts[from].disks[posts[from].top]; // from → toposts[from].disks[posts[from].top] = 0; // Lösche ursprüngliche Scheibeposts[from].top--; // Oberste Position am Pfosten from sinkt

} // transfervoid doPlay (int height, int from, int to, int temp) { // von from nach to mittels temp

if (height > 0) {doPlay(height - 1, from, temp, to); // von from nach temp mittels totransfer(from, to); // Bewege Scheibe from → todoPlay(height - 1, temp, to, from); // von temp nach to mittels from

} // if height > 0} // doPlaystatic void main (String [] args) {

int H = 4; Hanoi tower = new Hanoi(H); tower.display();tower.doPlay(H, Start, Finish, Temp); tower.display();

} // main} // Hanoi


Ablauf von Türme von Hanoi – (1)| | |

=== | |===== | |

======= | |

3, Start , Finish, Temp2, Start , Temp , Finish1, Start , Finish, Temp0, Start , Temp , Finish1, Start , Finish, Temp

| | || | |

===== | |======= === |

0, Temp , Finish, Start2, Start , Temp , Finish

| | || | || | |

======= === =====

1, Finish, Temp , Start0, Finish, Start , Temp1, Finish, Temp , Start

| | || | || | ===

======= | =====

0, Start , Temp , Finish3, Start , Finish, Temp

| | || | || | ===| ======= =====

2, Temp , Finish, Start1, Temp , Start , Finish0, Temp , Finish, Start1, Temp , Start , Finish

| | || | || | |

=== ======= =====

3 Scheiben


Ablauf von Türme von Hanoi – (2)0, Finish, Start , Temp2, Temp , Finish, Start

| | || | || ===== |

=== ======= |

1, Start , Finish, Temp0, Start , Temp , Finish1, Start , Finish, Temp

| | || === || ===== || ======= |

0, Temp , Finish, Start| | || === || ===== || ======= |

| | |=== | |

===== | |======= | |

========= | |4, Start , Finish, Temp3, Start , Temp , Finish2, Start , Finish, Temp1, Start , Temp , Finish0, Start , Finish, Temp1, Start , Temp , Finish

| | || | |

===== | |======= | |

========= | ===. . .

| | || === || ===== || ======= || ========= |

Mit 4 Scheiben


Hilbert Kurven• Eine Hilbert Kurve besteht aus den Teilkurven A, B, C, D• Die Kurven A0, B0, C0, D0 sind leer• Die Kurven Ai, Bi, Ci, Di sind definiert wie folgt

Ai

Di-1Ai-1

Ai-1 Bi-1

Bi

Bi-1Bi-1

Ci-1 Ai-1

Ci

Ci-1Di-1

Bi-1 Ci-1

Di

Ai-1Ci-1

Di-1 Di-1


A1

A2

D1A1

A1 B1

A2

A1

D1A1

A1 B1

D0A0

A0

B0


A1

A2

A3

A4

A5


Benutzung von Turtle-Graphics• Ein Stift (ein „Turtle“) bewegt sich auf dem Schirm• Steuerung durch ganz einfache Operationen

– home: Anfangsposition (Mitte des Zeichen-Bereiches)– setPen(x, y): Stift auf Punkt (x, y)– forward(x), backward(x): Bewegung um x Punkte

• forward(x) ≡ backward(-x)

– turnLeft(y), turnRight(y): Richtungsänderung um y Grad• turnLeft(y) ≡ turnRight(360 - y);

– turnTo(y): Richtung in Grad y• EAST = 0, SOUTH = 90, WEST = 180, NORTH = 270

– penUp, penDown: Stift heben bzw. senken– hideTurtle: Der Turtle selbst wird nicht gezeigt


Implementierung der Hilbert Kurve als Appletimport java.io.*;import java.awt.BorderLayout;import java.awt.Color;import java.applet.Applet;

public class Hilbert extends Applet {static final int W = 600, H = 600; // Breite und Höhe der Zeichenflächestatic final int EAST = 0, NORTH = 270, WEST = 180, SOUTH = 90;int u = W / 2; // Länge der Verbindungslinieint x = 0, y = 0; // Anfangsposition des StiftesColor [] colors = {Color.black, Color.blue, Color.cyan, Color.gray, Color.magenta};TurtleGraphicsPanel t;public void init() { // Methode init wird beim Laden des Applets aufgerufen

resize(W, H); // Zeichenfläche bestimment = new TurtleGraphicsPanel(); // Turtle-Instanz erzeugensetLayout(new BorderLayout());add("Center",t);

} // init

Inhalt der Hilbert.html Datei:<applet code="Hilbert.class" width=400 height=400></applet>Starten: appletviewer Hilbert.html


Implementierung der Hilbert Kurven – Ai, Bivoid A (int i) {

if (i > 0) {D(i - 1); t.turnTo(WEST); t.forward(u);A(i - 1); t.turnTo(SOUTH); t.forward(u);A(i - 1); t.turnTo(EAST); t.forward(u);B(i - 1);

} // if i} // A

void B (int i) {if (i > 0) {

C(i - 1); t.turnTo(NORTH); t.forward(u);B(i - 1); t.turnTo(EAST); t.forward(u);B(i - 1); t.turnTo(SOUTH); t.forward(u);A(i - 1);

} // if i} // B


Implementierung der Hilbert Kurven – Ci, Divoid C (int i) {

if (i > 0) {B(i - 1); t.turnTo(EAST); t.forward(u);C(i - 1); t.turnTo(NORTH); t.forward(u);C(i - 1); t.turnTo(WEST); t.forward(u);D(i - 1);

} // if i} // C

void D (int i) {if (i > 0) {

A(i - 1); t.turnTo(SOUTH); t.forward(u);D(i - 1); t.turnTo(WEST); t.forward(u);D(i - 1); t.turnTo(NORTH); t.forward(u);C(i - 1);

} // if i} // D


Implementierung der Hilbert Kurven – Startpublic void start() { // start wird von der Applet-Umgebung aufgerufen

t.clearScreen(); // Zeichenfläche löschent.hideTurtle(); // Turtle (ein kleines Dreieck) verstecken

for (int i = 1; i <= colors.length; i++) { x+= u / 2; // Anfangsposition für Kurvei

y+= u / 2; // Anfangsposition für Kurvei

t.setPen(x, y); // Stift auf die Anfangsposition t.setColor(colors[i - 1]); // Farbe für KurveiA(i); // Ai zeichnenu = u / 2; // Länge der Verbindungslinie setzen

} // for i

} // start} // Hilbert

Documents

und lokalen Variablen angelegt (gestapelt) • Die ... fileLászló Böszörményi ESOP Rekursive Algorithmen - 3 Ablauf der Fakultätsfunktion public class Faculty { // 18.09.2000