Prog. 1 Rekursion Beispiel Fakultät (iterativ)schwan/Vorlesungen/Prog1/Skripte/Prog1US8.pdf · Prog. 1 Rekursive Java-Implementierung • Rekursive Implementierung der Fakultät

02.12.2008 FH-Wiesbaden --- Medieninformatik --- WS 08/09 --- Prof. Dr. Ulrich Schwanecke 1

Prog. 1

Rekursion

Methoden knnen Methodenaufrufen

Methoden knnen nicht nur andere

Methoden aufrufen, sondern auch

sich selbst

Eine Methode, die sich selbst (direkt

oder indirekt) aufruft, nennt man

rekursiv

Viele Probleme (in der Informatik)

lassen sich durch Rekursionbesonders einfach und elegant lsen

Schon die Beschreibung eines

Problems kann interativ oderrekursiv geschehen

Das Rad des Theodorus (465 v. Chr.)

D1 : Rechtwinkeliges Dreieck mit Seitenlnge 1

D2 : Rechtwinkeliges Dreieck

Schenkel 1: Hypotenuse von D1

Schenkel 2: Seitenlnge 1

...

Dn : Rechtwinkeliges Dreieck

Schenkel 1: Hypotenuse von Dn-1

Schenkel 2: Seitenlnge 1

Mathematisch:


Prog. 1

n! = 1234...n

Beispiel Fakultt (iterativ)

Iterative Definition der Fakultt (Faktorielle) n! einer natrlichen Zahl n:

Die Lsung wird durch n-1 hintereinander ausgefhrte Multiplikationengewonnen

Schreiben Sie eine Funktion zur Berechnung der Fakultt von n:

static long fac(int n)

static long fac(int n) { long result = 1; for(int i=2; i 1

2. n! = 1 falls n = 1

Das Problem n! zu berechnen wurde auf das gleichartige, aber kleinereProblem (n-1)! zu berechnen zurckgefhrt (reduziert)

Zweite Zeile ist notwendig, damit man bei der wiederholten Anwendung der

ersten Zeile irgendwann zu einem Ende kommt


Prog. 1

Rekursive Java-Implementierung

Rekursive Implementierung der Fakultt

static long fact(int n) {

if(n==1) return 1; // Nicht rekursiver Zweig

else return fact(n-1)*n; // Rekursiver Zweig

}

Beispiel: Aufruf von fact(4)

Rekursiver Zweig:

1. fact(4) ruft fact(3) auf, bewahrt den Wert 4 in lokaler Variable n

2. fact(3) ruft fact(2) auf, bewahrt den Wert 3 in lokaler Variable n (verschieden von n aus 1.)

3. fact(2) ruft fact(1) auf, bewahrt den Wert 2 in lokaler Variable n (wiederum neue Variable)

Nicht rekursiver Zweig

fact(1) gibt den Wert 1 zurck

Auf dem Weg nach oben wird der vor dem rekursiven Aufruf ermittelte Wert mit der jeweiligen

lokalen Variablen n des Rufers multipliziert und das Ergebnis weiter nach oben gegeben


Prog. 1

Auswertung der Rekursion (logisch)static long fact(int n) {

if(n==1) return 1;

else return fact(n-1)*n;

}

Jeder Aufruf von fact besitzteigene lokale Variable

Werte sind in der Regelverschieden

Lokale Variablen aller geradelaufenden Methoden werden inMethodenkeller verwaltet

Die Datenstruktur Keller erlaubtdas Speichern und Lesen vonDaten

Zugriff nur auf zuletztgespeichertes Datum

Keller funktioniert also nachdem Last In First Out (LIFO)-Prinzip

Beim Aufruf einer Methodewerden ihre lokalen Variablenim Keller abgelegt

Beim Beenden einer Methodewerden ihre lokalen Variablenaus dem Keller entfernt

Beispiel: Aufruf von fact(4)

fact(1)

static long fact(int n) { if(n==1) return 1; else return fact(n-1)*n}


fact(2)


fact(3)

n=4static long fact(int n) { if(n==1) return 1; else return fact(n-1)*n}

n=3

n=2

n=1

1

2

6

=24


Prog. 1

Auswertung der Rekursion (Rechner)

Auswertung

Pro rekursivem Aufruf eine neue

Kopie der lokalen Variablen

Beispiel Fakultt

Parameter n

Lokale Variable result

Rckgabewert

Nicht sichtbar

// Funktion

static int fak(int n) {

if (n == 1) {

return 1;

} else {

int result = fak(n-1);

return result*n; }

!

4 ??

3 ??

2 ??

1 1?

4 246

3 62

2 21

n result !

Im Debugger nachvollziehen


Prog. 1

Manuelle Auswertung

// Funktion

static int fact(int n ) {

if (n == 1) {

return 1;

} else {

int result = fact(n-1);

return result*n; }

Was geben Sie zurck?

Ausfllen und an

Auftraggeber zurckgeben

Lokale Variablen

Knnen fr Ihre Berechnungen

benutzt werden

Ihre Eingabe

Ihr Auftraggeber

fllt das aus

stack frame

n result !

!


Prog. 1

Rekursion: Teile und Herrsche

Rekursion: Das Prinzip Teile und Herrsche:

Wenn das Problem trivial ist, dann lse es

Wenn das Problem nicht trivial ist, dann

Zerlege es in kleinere, unabhngige Teilprobleme

Lse die (kleineren) Teilprobleme separat

Verbinde die Teillsungen zu einer Gesamtlsung

Auf Englisch: divide and conquer

Abstraktes Schema

if(Problem ist klein genug (trivial))

fhre nichtrekursiven Zweig aus (lse Problem)

else

fhre rekursiven Zweig aus (zerlege Problem)

Rekursion liegt auch dann vor, wenn eine Methode p eine andere

Methode q aufruft und diese wiederum p aufruft. Unterscheidung:

indirekter Rekursion: Methode wird indirekt wieder aufgerufen

direkte Rekursion: Methode ruft sich (direkt) selbst wieder auf


Prog. 1

Vergleich: Iteration und Rekursion

Iteration Rekursion

Kein Funktionsaufruf der Funktion,

die definiert wird

Explizite Zustandsverwaltung in

lokaler Variablen

Schleifen

Funktionsaufruf der Funktion, die

definiert wird

Implizite Zustandsverwaltung durch

verschiedene Instanzen der

Parametervariablen

Keine Schleifen

static int fact(int n) {

int result = 1;

for (int i=2; i


Prog. 1

Verzweigte Rekursion (Beispiel: Fibonacci)

Der italienische Mathematiker Leonardo von Pisa besser bekannt unter dem

Namen Fibonacci (Kurzform von Filius Bonaccii) fragte sich eines Tages,

wieviele Kaninchen in einem eingezunten Gehege pro Jahres geborenwerden, wenn man davon ausgeht, dass

jeden Monat jedes Paar ein weiteres Paar erzeugt

Kaninchen zwei Monate nach Geburt geschlechtsreif sind

alle Kaninchen unsterblich sind

Mit Fn = Anzahl der Kaninchen Paare nach n Monaten gilt

F0=0, F1=1 und Fn=Fn-1+Fn-2

Die durch die Folge F0=0, F1=1 und Fn=Fn-1+Fn-2 definierten Zahlen heien

Fibonacci-Zahlen

Die ersten Fibonacci-Zahlen lauten

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...


Prog. 1

Berechnung der Fibonacci-Zahlen

Variante 1 (ineffizienter Algo.)static int fibo(int n) {

if(n==0 ||!n==1)

return n;

else

return fibo(n-1)+fibo(n-2);

}

Aufruf von fibo(n) erzeugt knapp

n*n Funktionsaufrufe Zwei Basisflle (triviale Flle)

Zweifach rekursiver Aufruf

Wiederholte Berechnung bereits

berechneter Werte

Bei 0.01sec pro Funktionsaufruf

bentigt fibo(40) ca. 16sec

Variante 2 (effizienter Algorithmus) int fibo(int n, int a, int b) {

if(n==0)

return a;

else

return fibo(n-1, b, a+b);

}

Aufruf von fibo(n, 0, 1) erzeugt

n+1 Funktionsaufrufe

Bei 0.01sec pro Funktionsaufruf

bentigt fibo(40, 0, 1) ca. 0.4sec

Iterative Lsung:int fibo(int n) {

int[] f = new int[n+1];

f[0] = 0; f[1] = 1;

for(int i=2; i


Prog. 1

Trme von Hanoi (praktisch)

1

2

3

4 8

7

6

5


Prog. 1

Trme von Hanoi (algorithmisch)

Rekursive Lsung Falls nur eine Scheibe (n=1)

Bewege Scheibe von Quelle nach Ziel

Falls mehrere Scheiben (n>1)

1. Bewege Turm aus den n-1 obersten Scheiben zum Arbeitsbereich

2. Bewege n-te Scheibe zum Ziel

3. Bewege Turm aus n-1 obersten Scheiben vom Arbeitsbereich zum Ziel

Wieviele Zge erfordert die Lsung?

xn=Anzahl Zge, um n Scheiben von einer Stange auf eine andere zu bewegen

Nach obiger Strategie x1=1 und x

n=x

n-1+1+x

n-1 =2x

n-1+1 fr n=2,3,...

Also xn = 2n-1+2n-2+...+22+2+1 = 2n-1

Flinke Mnche (1 Sekunde pro Scheibenwechsel) brauchen fr die 64 Scheiben also

264-1=18.446.744.073.709.551.615sec oder rund 580Milliarden Jahre


Prog. 1

Trme von Hanoi (in Java)

static void hanoi(int n, int src, int work, int dest ) { if(n==1) { System.out.print("Bewege Scheibe von "); System.out.println(src + " nach " + dest); } else { hanoi(n-1, src, dest, work); System.out.print("Bewege Scheibe von "); System.out.println(src + " nach " + dest); hanoi(n-1, work, src, dest);

} }

static void hanoi(int n, int src, int work, int dest ){ if(n>1) hanoi(n-1, src, dest, work); System.out.print("Bewege Scheibe von "); System.out.println(src + " nach " + dest); if(n>1) hanoi(n-1, work, src, dest);}


Prog. 1

Trme von Hanoi (iterativ I)static void hanoiIterative(int n)"{" // n has to be greater than 1

int [][] bars = new int[3][n+1]; // src, work, dest bar, containing discs

int [] lastPos = {n, 0, 0}; // start configuration"

int posSDisc = 0; // smallest disc is on source

for (int i=0; i bars[pos2][lastPos[pos2]]) {

System.out.printf("-------> Disc from %d to %d\n", pos2, pos1);

bars[pos1][++lastPos[pos1]] = bars[pos2][lastPos[pos2]];

bars[pos2][lastPos[pos2]--] = 0;

} else if (bars[pos1][lastPos[pos1]] < bars[pos2][lastPos[pos2]]) {


bars[pos2][++lastPos[pos2]] = bars[pos1][lastPos[pos1]];

bars[pos1][lastPos[pos1]--] = 0; } }}


Prog. 1

Trme von Hanoi (iterativ II)static void hanoiIterative2(int n) {

int [][] bars = new int[3][n+1]; // src, work, dest bar

int [] last = {n, 0, 0}; // start configuration

int pS=0, pos1, pos2; // smallest disc on source"

for (int i=0; ibars[(pS+2)%3][last[(pS+2)%3]]) ?

(pS+2)%3 : (pS+1)%3; // disc to only possible place

pos1 = 2*(pS+pos2) % 3;

if (bars[pos1][last[pos1]] != bars[pos2][last[pos2]]) {


bars[pos1][++last[pos1]] = bars[pos2][last[pos2]];

bars[pos2][last[pos2]--] = 0;

}

}

}


Prog. 1

Trme von Hanoi (knstlerisch)


Prog. 1

Verschachtelte Rekursion

Prinzip

Argument des rekursiven Aufrufs wird selbst durch rekursiven Aufrufbestimmt

In jeder Programmiersprache mit Rekursion nutzbar

Ausfhrung wieder mit lokalen Variablen und Stapel

Beispiel

Ackermannfunktion

Sehr schnell wachsende Funktion

Sehr aufwendige Berechnung

int ackermann(int m, int n) {

if (m == 0)

return n+1;

if (n == 0)

return ackermann(m-1, 1);

return ackermann(m-1, ackermann(m,n-1));

}


Prog. 1

Zusammenfassung Rekursion

Rekursion Eine Funktion ruft sich selbst (direkt oder indirekt) auf

Die Rekursion endet immer bei trivialen Fllen

Vorteile der Rekursion Einfache, mchtige, intuitive Darstellung und Formulierung vieler Algorithmen

Prinzip der Problemreduktion (Teile und Herrsche) direkt implementierbar

Legenden um die Rekursion Rekursion ist immer langsamer

Rekursion geht nicht in allen Umgebungen

Rekursion braucht man nicht

Fakten zur Rekursion Iteration und Rekursion sind gleich ausdrucksstark

Alle sinnvollen Programmierumgebungen untersttzen Rekursion

Rekursion kann (fast) immer so effizient wie ein iterativer Algorithmusimplementiert und ausgefhrt werden

Ohne Rekursion werden Programm meist lnger, unbersichtlicher,unwartbar, teuer, unelegant, ...

Documents

Prog. 1 Rekursion Beispiel Fakultät (iterativ)schwan/Vorlesungen/Prog1/Skripte/Prog1US8.pdf · Prog. 1 Rekursive Java-Implementierung • Rekursive Implementierung der Fakultät