12. Rekursion Grundlagen der Programmierung 1 (Java) · PDF file12. Rekursion Prof. Dr. Bernhard Humm FH Darmstadt, 24. Januar 2006 Grundlagen der Programmierung 1 (Java) Fachhochschule

12. Rekursion
Prof. Dr. Bernhard Humm
FH Darmstadt, 24. Januar 2006
Grundlagen der
Programmierung 1 (Java)
Fachhochschule Darmstadt
Haardtring 100
D-64295 Darmstadt

Seite 224.1.2006,Bernhard Humm: Grundlagen der Programmierung I (Java). FH Darmstadt, WS 2005/2006
Einordnung im Kontext der Vorlesung
1. Einfhrung
2. Einfache Programme
3. Kontrollstrukturen
4. Objekt-Orientierung I
5. Algorithmen und Datenstrukturen I
6. Interfaces
8. Parametrisierte Typen (Generics)
7. Pakete
12. Rekursion
9. Fehler und Ausnahmen
13. Algorithmen und Datenstrukturen II
14. Objektorientierung II
11. Komponenten
15. Design
16. Die Java Klassenbibliothek I
17. Die Java Klassenbibliothek II
10. Gutes Programmieren

Definition
Beispiele
Eigenschaften rekursiver Algorithmen
Definition
Agenda

Definition von Rekursion
Beispiel: Fakultt
Eine Methode m() heit rekursiv, wenn sie sich selbst aufruft
m() m() direkt rekursiv
m() n() m() indirekt rekursiv
Beispiel: Berechnung der Fakultt (n!)
n! = 1 * 2 * 3 * ... * (n-1) * n
(n-1)!
rekursive Definition
n! = (n-1)! * n
1! = 1
Rekursive Methode zur Berechnung der Fakultt
long fact (long n) {
if (n == 1)
return 1;
else
return fact(n-1) * n;
}
Allgemeines Muster
if (Problem klein genug)
nichtrekursiver Zweig;
else
rekursiver Zweig

Ablauf einer rekursiven Methode
Beispiel: Fakultt
long fact (long n) {if (n == 1) return 1else return fact(n-1) * n;
}
n = 4Jede Aktivierung von fact hat ihr eigenes n
und rettet es ber den rekursiven Aufruf hinweg
}
n = 3
}
n = 2
}
n = 1 1
6
24
2

Definition
Beispiele
Beispiele
Agenda

Beispiel: binres Suchen rekursiv
z.B. Suche von 17 (Array muss sortiert sein)
2
0
3
1
5
2
7
3
11
4
13
5
17
6
19
7
low m high
a Index m des mittleren Element bestimmen
17 > a[m] in rechter Hlfte weitersuchen
2
0
3
1
5
2
7
3
11
4
13
5
17
6
19
7
low m high
a
static int search (int elem, int[] a, int low, int high) {
if (low > high) return -1; // empty
int m = (low + high) / 2;
if (elem == a[m]) return m;
if (elem < a[m]) return search(elem, a, low, m-1);
return search(elem, a, m+1, high);
}
nichtrekursiver Zweig
rekursiver Zweig

2 3 5 7 11 13 17 19
Ablauf des rekursiven binren Suchens
static int search (int elem, int[] a, int low, int high) {if (low > high) return -1;int m = (low + high) / 2;if (elem == a[m]) return m;if (elem < a[m]) return search(elem, a, low, m-1);return search(elem, a, m+1, high);
}
low high
0 1 2 3 4 5 6 7
m
6
elem = 17, low = 0, high = 7 6
m = 3
}
2 3 5 7 11 13 17 19
low high
0 1 2 3 4 5 6 7
m
low = 4, high = 7
m = 5
}
2 3 5 7 11 13 17 19
low
m
high
0 1 2 3 4 5 6 7
low = 6, high = 7
m = 6
6

Beispiel: grter gemeinsamer Teiler
static int gcd (int x, int y) {
int rest = x % y;
while (rest != 0){
x = y; y = rest;
rest = x % y;
}
return y;
}
static int gcd (int x, int y)
{
int rest = x % y;
if (rest == 0) return y;
else return gcd(y, rest);
}
rekursiv iterativ

Beispiel: Die Trme von Hanoi
Gegeben sind 3 Pfosten mit n Scheiben
(unterschiedlicher Gre)
Grundstellung: alle Scheiben nach Gre
geordnet auf Pfosten A
Ziel: Lege alle n Scheiben von A nach C
Restriktion 1: jeweils nur eine Scheibe darf bewegt werden
Restriktion 2: niemals darf eine grere auf einer kleineren Scheibe liegen
Lsungsstrategie:
Problem allg. fr Turm der Hhe n lsen; folgende Flle sind zu unterscheiden
n = 0: gar nichts machen
n > 0:
(1) Turm der Hhe n-1 von A nach B bewegen (mittels C)
(2) Scheibe von A nach C legen
(3) Turm der Hhe n - 1 von B nach C bewegen (mittels A)
A B C

Beispiel: Trme von Hanoi
Rekursiver Algorithmus
import java.io.*;
public class Hanoi {
public static void verlegeTurm(int hoehe, int von,
int nach, int ueber) {
if (hoehe > 0) {
verlegeTurm(hoehe-1, von, ueber, nach);
System.out.println("von "+von + " nach "+ nach);
verlegeTurm(hoehe-1, ueber, nach, von);
}
}
public static void main(String[] args) throws IOException {
BufferedReader in = Text.open(System.in);
int hoehe = Text.readInt(in);
verlegeTurm(hoehe, 1, 2, 3);
}
}
A B C

Beispiel: Fibonacci-Funktion
Rekursiver Algorithmus
Fibonacci-Funktion
fib(n) = 1 fr n= 1, 2 und
fib(n) = fib(n-1) + fib(n-2) fr n > 2
Rekursiver Algorithmus zur Berechnung der Fibonacci-Zahlen
public class Fib {
public static int fib(int n) {
if (n

Effizienzuntersuchung Fibonacci:
Rekursive Implementierung
da bei Aufrufen der fib()-Methode stets die gleichen Schritte ausgefhrt werden,
ist Aufwand (mit c bezeichnet) proportional zur Anzahl der Aufrufe der Methode
Abschtzung Anzahl rekursiver Aufrufe von fib in Abhngigkeit von n
es gilt: c1 = c2 = 1
fr n > 2: cn = 1 + cn-1 + cn-2bei n > 3: cn-1= 1 + cn-2 + cn-3, also cn-2 = cn-1 - 1 - cn-3.
Einsetzen von cn-1 in Gleichung cn
cn = 2 + 2cn-2 + cn-3 > 2cn-2 > 22cn-4 > 2
3cn-6 > ...> 2n DIV2-1c2
also cn > 2n DIV2-1 (ist eine Untergrenze fr cn)
cn = 1 + cn-1 + cn-2 = 2cn-1 - cn-3 < 2cn-1< 22cn-2

Effizienzuntersuchung Fibonacci-Funktion:
Iterative Implementierung
Abschtzung der Anzahl der ausgefhrte Schritte (Anweisungen)
cn = 5 + (n-2)*3 + 1
iterative Fibonacci-Algorithmus erfordert mit n linear wachsenden Aufwand
public static long fibIt(int n) {
long fibN = 0;
long fibN1 = 1; // fuer Fib(n-1);
long fibN2 = 1; // fuer Fib(n-2);
if (n == 1) return 1;
else if (n == 2) return 1;
for (int i=3; i

Beispiel: Ackermann-Funktion
ack(n,m) =
m + 1 falls n=0
ack(n-1,1) falls m=0
ack(n-1,ack(n,m-1)) sonst
Vorsicht: Funktion wchst sehr stark: ack(4,2) besitzt 19729 Stellen
ack(4,4) ist grer als 10 hoch 10 hoch 10 hoch 1900
public static int ack(int n, int m) {
if (n == 0)
return m + 1;
else if (m == 0)
return ack(n-1,1);
else
return ack(n-1,ack(n,m-1));
}

Definition
Beispiele
Agenda

Vor- und Nachteile rekursiver Algorithmen
Anmerkung
zu jedem rekursiv formulierten Algorithmus gibt es einen quivalenten iterativen
Algorithmus
Vorteile rekursiver Algorithmen
krzere Formulierung
leichter

Documents

12. Rekursion Grundlagen der Programmierung 1 (Java) · PDF file12. Rekursion Prof. Dr. Bernhard Humm FH Darmstadt, 24. Januar 2006 Grundlagen der Programmierung 1 (Java) Fachhochschule