[SOLVED] CS compiler Programmierung Klassifikation rekursiver Methoden

Programmierung Klassifikation rekursiver Methoden
auf der Basis von Folien v. V Gruhn
Michael Goedicke
[email protected]
paluno

Rekursion: Klassifikation rekursiver Methoden
Definition: Eine rekursive Methode heit linear-rekursiv, wenn in den einzelnen Zweigen der bedingten Anweisung, die die rekursiven Aufrufe steuert, jeweils hochstens ein Aufruf der Methode vorkommt.
Die fakultaet(int)-Methode ist linear-rekursiv:
public int fakultaet(int n) { if (n == 1) {
return 1;
} else {
return n * fakultaet(n 1);
rekursiver Methodenaufruf kommt nur einmal vor
} }
Zweige der bedingten Anweisung, die die rekursiven Aufrufe steuert
M. Goedicke Programmierung WiSe 2020/2021 2
paluno

Rekursion: Klassifikation rekursiver Methoden
Der Mathematiker Leonardo Fibonacci stellte 1202 die Frage, wie viele Kaninchenparchen es nach n Jahren gibt, wenn
im ersten Jahr genau ein Parchen existiert,
jedes Parchen, das mindestens zwei Jahre alt ist, jedes Jahr ein neues
Parchen zur Welt bringt und
die Kaninchen eine unendliche Lebensdauer haben.
Sei fn die Anzahl der Kaninchenparchen nach n Jahren. Dann heit (fn)n1 = (f1, f2, f3, f4, ) Fibonacci-Folge. Offenbar giltf1 = 1,f2 = 1undfn = fn-1 + fn-2 furn 2.
public int fibonacci(int n) {
if (n <= 2) {return 1; } else {return fibonacci(n – 1) + fibonacci(n 2); }}M. Goedicke Programmierung WiSe 2020/2021 3 paluno Rekursion: Klassifikation rekursiver Methoden Die fibonacci(int)-Methode ist nicht linear-rekursiv:public int fibonacci(int n) { if (n <= 2) { return 1; } else {return fibonacci(n – 1) + fibonacci(n 2); }}rekursiver Methodenaufruf kommt zweimal vor Definition: Eine linear-rekursive Methode heit schlicht oder endrekursiv, wenn der rekursive Aufruf als letztes ausgewertet wird. Die fakultaet(int)-Methode ist nicht endrekursiv, da nach der Auswertung von fakultaet(n – 1) noch multipliziert wird. M. Goedicke Programmierung WiSe 2020/2021 4 paluno Rekursion: Klassifikation rekursiver Methoden public boolean istGerade1(int n) {if (n <= 1) {return n == 0; } else {} }wird als letztes ausgewertetpublic boolean istGerade2(int n) {if (n == 0) {return true; } else {return !istGerade2(n – 1);} }Die Methode istGerade1(int) ist return istGerade1(n – 2); endrekursiv: der rekursive Aufruf Die Methode istGerade2(int) ist nicht endrekursiv: der rekursive Aufruf wird noch negiert. M. Goedicke Programmierung WiSe 2020/2021 5 paluno Rekursion: Transformation endrekursiver Methoden Beobachtung: Sei G endrekursiv. Dann gibt es eine Aussage P(x) sowie zwei Funktionen und mit der Eigenschaft: Wenn P(x) erfullt ist, dann gilt G(x) = (x). Andernfalls gilt G(x) = G((x)). Diese Beobachtung kann unmittelbar in eine generische Methode umgesetzt werden:public S gRekursiv(T x) { if (P(x)) {
return (x);
} else {
return gRekursiv((x)); }
}
Bemerkung: Das Argument x kann auch eine Liste sein, d.h. es kann x = (x1,,xn) gelten.
M. Goedicke Programmierung WiSe 2020/2021 6
paluno

Rekursion: Transformation endrekursiver Methoden
Der Terminierungsbedingung wird immer erreicht, wenn es fur alle x eine naturliche Zahl m 0 mit der Eigenschaft P(m(x)) gibt. Dabei ist 0(x) = x und k(x) = (k-1(x)) fur k > 0.
Behauptung: Sei n die kleinste naturliche Zahl mit der Eigenschaft P(n(x)). Dann gilt G(x) = (n(x)).
Beweis durch vollstandige Induktion uber n:
Induktionsverankerung: Wenn n = 0 gilt, dann ist P(x) erfullt. Daraus folgt
unmittelbar G(x) = (x) = (0(x)).
Induktionsvoraussetzung: Die Behauptung gilt fur alle x, fur die n die kleinste
naturliche Zahl mit der Eigenschaft P(n(x)) ist.
Induktionsschritt: Sei n+1 die kleinste naturliche Zahl mit der Eigenschaft P(n+1(x))und seix1 = (x). Dan + 1 > n 0gilt, istG(x) = G((x)) = G(x1) nach Definition von G.
Auerdem ist n die kleinste naturliche Zahl, fur die P(n(x1)) erfullt ist. Die Anwendung der Induktionsvoraussetzung liefert:
G(x) = G(x1) = (n(x1)) = (n((x))) = (n+1(x))
M. Goedicke Programmierung WiSe 2020/2021 7
paluno

Rekursion: Transformation endrekursiver Methoden
Mit Hilfe der Formel G(x) = (n(x)) ist eine systematische Transformation der endrekursiven Methode gRekursiv(T) in eine iterative Methode moglich.
Die Folge x, (x), 2(x), , n(x) wird dabei in einer Schleife berechnet:
public S gIterativ(T x) {
T x1 = x, tx;
while (!P(x1)) { tx = (x1);
x1 = tx; }
return (x1);
}
Diese Transformation wird von einigen Compilern automatisch durchgefuhrt.
M. Goedicke Programmierung WiSe 2020/2021 8
paluno

Rekursion: Transformation endrekursiver Methoden
Behauptung: Sei n die kleinste naturliche Zahl mit der Eigenschaft P(n(x)). Dann gilt gIterativ(x) = (n(x)).
Beweis durch vollstandige Induktion:
Induktionsverankerung: Wenn n = 0 gilt, dann ist P(x) erfullt, sodass die while-Schleife in Zeile 4 nicht betreten wird. In diesem Fall gilt in Zeile 6 also x1 = x, woraus gIterativ(x) = (x) folgt.
Induktionsvoraussetzung: Die Behauptung gilt fur alle x, fur die n die kleinste naturliche Zahl ist, so dass P(n(x)) erfullt ist.
T x1 = x, tx;
while (!P(x1)) { tx = (x1);
x1 = tx; }
return (x1);
M. Goedicke Programmierung WiSe 2020/2021 9
// 4
// 6
paluno

Rekursion: Transformation endrekursiver Methoden
Behauptung: Sei n die kleinste naturliche Zahl mit der Eigenschaft P(n(x)). Dann gilt gIterativ(x) = (n(x)).
Beweis durch vollstandige Induktion:
Induktionsschritt: Sei n+1 die kleinste naturliche Zahl mit der Eigenschaft P(n+1(x)). Da n+1 > n 0 gilt, ist P(x) nicht erfullt. Daher wird die while-Schleife in Zeile 4 mindestens einmal betreten.
T x1 = x, tx;
while (!P(x1)) { tx = (x1);
x1 = tx; }
// 4
return (x1);
M. Goedicke Programmierung WiSe 2020/2021 10
paluno

Rekursion: Transformation endrekursiver Methoden
Behauptung: Sei n die kleinste naturliche Zahl mit der Eigenschaft P(n(x)). Dann gilt gIterativ(x) = (n(x)).
Beweis durch vollstandige Induktion:
Die Methode kann daher in diesem Fall umformuliert werden, indem man dafur sorgt, dass die Anweisungen des Schleifenrumpfs vor dem ersten Betreten der Schleife ausgefuhrt werden.
T x1 = x, tx;
while (!P(x1)) { tx = (x1);
x1 = tx; }
return (x1);
M. Goedicke Programmierung WiSe 2020/2021 11
tx = (x1);
x1 = tx;
paluno

Rekursion: Transformation endrekursiver Methoden
Behauptung: Sei n die kleinste naturliche Zahl mit der Eigenschaft P(n(x)). Dann gilt gIterativ(x) = (n(x)).
Beweis durch vollstandige Induktion:
Anschlieend kann die Initialisierungsanweisungen in Zeile 1 angepasst
werden. Diese Umformulierungen zeigen, dass in diesem Fall gilt:
gIterativ(x) = gIterativ((x))
T x1 = (x), tx;
while (!P(x1)) { tx = (x1);
x1 = tx; }
// 1
return (x1);
M. Goedicke Programmierung WiSe 2020/2021 12
paluno

Rekursion: Transformation endrekursiver Methoden
Behauptung: Sei n die kleinste naturliche Zahl mit der Eigenschaft P(n(x)). Dann gilt gIterativ(x) = (n(x)).
Beweis durch vollstandige Induktion:
Da n die kleinste naturliche Zahl mit der Eigenschaft P(n((x))) ist, kann man die Induktionsvoraussetzung anwenden:
gIterativ(x) = gIterativ((x)) = (n((x))) = (n+1(x))
T x1 = (x), tx;
while (!P(x1)) { tx = (x1);
x1 = tx; }
return (x1);
M. Goedicke Programmierung WiSe 2020/2021 13
paluno

Rekursion: Transformation endrekursiver Methoden
Insgesamt haben wird gezeigt, dass gIterativ(T) tatsachlich die iterative Version von gRekursiv(T) ist.
public S gRekursiv(T x) { if (P(x)) {
return (x);
} else {
return gRekursiv((x)); }
}
public S gIterativ(T x) {
T x1 = x, tx;
while (!P(x1)) {
tx = (x1);
x1 = tx; }
return (x1);
}
Systematische Transformation einer endrekursiven Methode in eine iterative Methode
M. Goedicke Programmierung WiSe 2020/2021 14
paluno

Rekursion: Transformation endrekursiver Methoden
Beispiel: Seien x und y ganze Zahlen mit x y = 0. Auerdem sei P(x,y) :y = 0,
(x,y)=xund
(x,y) = (y,x mod y),
wobei x mod y den Rest der ganzzahligen Division von x durch y bezeichnet. Dann gilt G(x,y) = ggT(x,y).
Die Definition kann man nun in eine iterative Methode umsetzen:
public int ggT(int x, int y) { int x1 = x, y1 = y, tx, ty; while (y1 != 0) {
tx = y1;
ty = x1 % y1; x1 = tx;
y1 = ty;
}
return x1; }
M. Goedicke Programmierung WiSe 2020/2021 15
paluno

Rekursion: Fibonacci-Folge
Methoden, die nicht linear-rekursiv sind, konnen ebenfalls in iterative Methoden transformiert werden.
Wir uberlegen uns beispielhaft, wie man fibonacci(int) in eine iterative Methode transformieren kann.
Erinnerung: fibonacci(n) berechnet die n-te Fibonacci-Zahl fn, wobeif1 = 1,f2 = 1undfk+2 = fk+1 + fk gilt.
Bei der Berechnung von fn mussen viele Zwischenergebnisse mehrfach berechnet werden:
f6
f5
f4 f3 f3 f2
f3 f2 f2 f1 f2 f1 f2 f1
f4
M. Goedicke Programmierung WiSe 2020/2021 16
paluno

Rekursion: Fibonacci-Folge
Wir fuhren zwei akkumulierende Parameter ein, in denen die Zwischenergebnisse gespeichert werden.
Sei fiboAux(n,a,b) = fiboAux(n 1,b,a + b) fur n 1 und fiboAux(1,a,b) = a.
Da fiboAux endrekursiv ist, kann man fiboAux in eine iterative Methode umsetzen.
Wir mussen also nur noch zeigen, dass man fn mit Hilfe der Funktion fiboAux berechnen kann.
Beispiel: Sein = 6,a = f1 undb = f2. Es gilt:
fiboAux(6,f1,f2) = fiboAux(5,f2,f1 + f2)
= fiboAux(5,f2,f3) = fiboAux(4,f3,f2 + f3)
= fiboAux(4,f3,f4) = fiboAux(3,f4,f3 + f4)
= fiboAux(3,f4,f5) = fiboAux(2,f5,f4 + f5)
= fiboAux(1,f5,f6) = fiboAux(1,f6,f5 + f6) = f6
Daraus leiten wir die Vermutung fiboAux(n,f1,f2) = fn ab.
M. Goedicke Programmierung WiSe 2020/2021 17
paluno

Rekursion: Fibonacci-Folge
Behauptung: Fur alle k mit der Eigenschaft 1 k n gilt fiboAux(k,fn-k+1,fn-k+2) = fn.
Beweis durch vollstandige Induktion uber k:
Induktionsverankerung: Die Behauptung gilt fur k = 1 nach Definition von
fiboAux.
Induktionsvoraussetzung: Es gelte fiboAux(k,fn-k+1,fn-k+2) = fn fur ein
festes k < n.Induktionsschritt: Nach Definition von fiboAux gilt:fiboAux(k + 1,fn-(k+1)+1,fn-(k+1)+2) = fiboAux(k + 1,fn-k,fn-k+1)= fiboAux(k,fn-k+1,fn-k + fn-k+1) = fiboAux(k,fn-k+1,fn-k+2)Die Anwendung der Induktionsvoraussetzung liefert:fiboAux(k + 1,fn-(k+1)+1,fn-(k+1)+2) = fn Folgerung: Mit k = n erhalten wir fiboAux(n,f1,f2) = fn.M. Goedicke Programmierung WiSe 2020/2021 18 paluno Rekursion: Fibonacci-Folge Mit Hilfe der Funktion fiboAux erhalten wir nun eine endrekursive Version der Methode fibonacci(int):public int fibonacciEndrekursiv(int n) { return fiboAuxRekursiv(n, 1, 1);}private int fiboAuxRekursiv(int n, int a, int b) { if (n == 1) {return a; } else {return fiboAuxRekursiv(n – 1, b, a + b); }}fiboAuxRekursiv(6,1,1)M. Goedicke Programmierung WiSe 2020/2021 19 paluno Rekursion: Fibonacci-Folge Mit Hilfe der Funktion fiboAux erhalten wir nun eine endrekursive Version der Methode fibonacci(int):public int fibonacciEndrekursiv(int n) { return fiboAuxRekursiv(n, 1, 1);}private int fiboAuxRekursiv(int n, int a, int b) { if (n == 1) {return a; } else {return fiboAuxRekursiv(n – 1, b, a + b); }}fiboAuxRekursiv(5,1,2) fiboAuxRekursiv(6,1,1) fiboAuxRekursiv(6,1,1)M. Goedicke Programmierung WiSe 2020/2021 20 paluno Rekursion: Fibonacci-Folge Mit Hilfe der Funktion fiboAux erhalten wir nun eine endrekursive Version der Methode fibonacci(int):public int fibonacciEndrekursiv(int n) { return fiboAuxRekursiv(n, 1, 1);}private int fiboAuxRekursiv(int n, int a, int b) { if (n == 1) {return a; } else {return fiboAuxRekursiv(n – 1, b, a + b); }}fiboAuxRekursiv(4,2,3) fiboAuxRekursiv(5,1,2) fiboAuxRekursiv(6,1,1) fiboAuxRekursiv(5,1,2) fiboAuxRekursiv(6,1,1) fiboAuxRekursiv(6,1,1)M. Goedicke Programmierung WiSe 2020/2021 21 paluno Rekursion: Fibonacci-Folge Mit Hilfe der Funktion fiboAux erhalten wir nun eine endrekursive Version der Methode fibonacci(int):public int fibonacciEndrekursiv(int n) { return fiboAuxRekursiv(n, 1, 1);}private int fiboAuxRekursiv(int n, int a, int b) { if (n == 1) {return a; } else {return fiboAuxRekursiv(n – 1, b, a + b); }}fiboAuxRekursiv(3,3,5) fiboAuxRekursiv(4,2,3) fiboAuxRekursiv(5,1,2) fiboAuxRekursiv(6,1,1) fiboAuxRekursiv(4,2,3) fiboAuxRekursiv(5,1,2) fiboAuxRekursiv(6,1,1) fiboAuxRekursiv(5,1,2) fiboAuxRekursiv(6,1,1) fiboAuxRekursiv(6,1,1)M. Goedicke Programmierung WiSe 2020/2021 22 paluno Rekursion: Fibonacci-Folge Die endrekursive Methode fibonacciEndrekursiv(int) kann nun in eine iterative Methode transformiert werden: public int fibonacciIterativ(int n) { return fiboAuxIterativ(n, 1, 1);} private int fiboAuxIterativ(int n, int a, int b) { int n1 = n, a1 = a, b1 = b, tn, ta, tb; while (n1 > 1) {
tn = n1 1;
ta = b1;
tb = a1 + b1;
n1 = tn;
a1 = ta;
b1 = tb; }
return a1; }
M. Goedicke Programmierung WiSe 2020/2021 23
paluno

Rekursion: Rekursive Datenstrukturen
Die Methode isMember(T) ist endrekursiv und kann daher mit Hilfe des vorgestellten Verfahrens in eine iterative Methode transformiert werden:
public boolean isMemberIterativ(T x) { RekursiveListe liste = this;
while(liste != null && !x.equals(liste.element)) {
liste = liste.liste;
}
return liste != null;
}
T
RekursiveListe
+element:T +liste:RekursiveListe
+isMember(T):boolean +isMemberIterativ(T):boolean
M. Goedicke Programmierung WiSe 2020/2021 24
paluno

Rekursive Methoden: Zusammenfassung
Man unterteilt rekursive Methoden in endrekursive Methoden, linear- rekursive Methoden und Methoden, die nicht linear-rekursiv sind.
(strikt)Endrekursive Methode konnen leicht in iterative Methoden transformiert werden.
M. Goedicke Programmierung WiSe 2020/2021 25
paluno