CS计算机代考程序代写 compiler Programmierung Klassifikation rekursiver Methoden

Programmierung Klassifikation rekursiver Methoden
auf der Basis von Folien v. V Gruhn
Michael Goedicke
michael.goedicke@paluno.uni-due.de
© paluno

Rekursion: Klassifikation rekursiver Methoden
▪ Definition: Eine rekursive Methode heißt linear-rekursiv, wenn in den einzelnen Zweigen der bedingten Anweisung, die die rekursiven Aufrufe steuert, jeweils höchstens 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 Kaninchenpärchen es nach n Jahren gibt, wenn
• im ersten Jahr genau ein Pärchen existiert,
• jedes Pärchen, das mindestens zwei Jahre alt ist, jedes Jahr ein neues
Pärchen zur Welt bringt und
• die Kaninchen eine unendliche Lebensdauer haben.
▪ Sei fn die Anzahl der Kaninchenpärchen nach n Jahren. Dann heißt (fn)n≥1 = (f1, f2, f3, f4, …) Fibonacci-Folge. Offenbar giltf1 = 1,f2 = 1undfn = fn-1 + fn-2 fürn ≥ 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 heißt 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 ausgewertet public 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) erfüllt 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 für alle x eine natürliche Zahl m ≥ 0 mit der Eigenschaft P(μm(x)) gibt. Dabei ist μ0(x) = x und μk(x) = μ(μk-1(x)) für k > 0.
▪ Behauptung: Sei n die kleinste natürliche Zahl mit der Eigenschaft P(μn(x)). Dann gilt G(x) = ν(μn(x)).
▪ Beweis durch vollständige Induktion über n:
Induktionsverankerung: Wenn n = 0 gilt, dann ist P(x) erfüllt. Daraus folgt
unmittelbar G(x) = ν(x) = ν(μ0(x)).
Induktionsvoraussetzung: Die Behauptung gilt für alle x, für die n die kleinste
natürliche Zahl mit der Eigenschaft P(μn(x)) ist.
Induktionsschritt: Sei n+1 die kleinste natürliche 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.
Außerdem ist n die kleinste natürliche Zahl, für die P(μn(x1)) erfüllt 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 möglich.
▪ 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 durchgeführt.
M. Goedicke – Programmierung WiSe 2020/2021 8
© paluno

Rekursion: Transformation endrekursiver Methoden
▪ Behauptung: Sei n die kleinste natürliche Zahl mit der Eigenschaft P(μn(x)). Dann gilt gIterativ(x) = ν(μn(x)).
▪ Beweis durch vollständige Induktion:
Induktionsverankerung: Wenn n = 0 gilt, dann ist P(x) erfüllt, 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 für alle x, für die n die kleinste natürliche Zahl ist, so dass P(μn(x)) erfüllt 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 natürliche Zahl mit der Eigenschaft P(μn(x)). Dann gilt gIterativ(x) = ν(μn(x)).
▪ Beweis durch vollständige Induktion:
Induktionsschritt: Sei n+1 die kleinste natürliche Zahl mit der Eigenschaft P(μn+1(x)). Da n+1 > n ≥ 0 gilt, ist P(x) nicht erfüllt. 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 natürliche Zahl mit der Eigenschaft P(μn(x)). Dann gilt gIterativ(x) = ν(μn(x)).
▪ Beweis durch vollständige Induktion:
Die Methode kann daher in diesem Fall umformuliert werden, indem man dafür sorgt, dass die Anweisungen des Schleifenrumpfs vor dem ersten Betreten der Schleife ausgeführt 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 natürliche Zahl mit der Eigenschaft P(μn(x)). Dann gilt gIterativ(x) = ν(μn(x)).
▪ Beweis durch vollständige Induktion:
Anschließend 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 natürliche Zahl mit der Eigenschaft P(μn(x)). Dann gilt gIterativ(x) = ν(μn(x)).
▪ Beweis durch vollständige Induktion:
Da n die kleinste natürliche 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) tatsächlich 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. Außerdem 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, können ebenfalls in iterative Methoden transformiert werden.
▪ Wir überlegen 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 müssen 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 führen zwei akkumulierende Parameter ein, in denen die Zwischenergebnisse gespeichert werden.
▪ Sei fiboAux(n,a,b) = fiboAux(n – 1,b,a + b) für n ≥ 1 und fiboAux(1,a,b) = a.
▪ Da fiboAux endrekursiv ist, kann man fiboAux in eine iterative Methode umsetzen.
▪ Wir müssen 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: Für alle k mit der Eigenschaft 1 ≤ k ≤ n gilt fiboAux(k,fn-k+1,fn-k+2) = fn.
▪ Beweis durch vollständige Induktion über k:
Induktionsverankerung: Die Behauptung gilt für k = 1 nach Definition von
fiboAux.
Induktionsvoraussetzung: Es gelte fiboAux(k,fn-k+1,fn-k+2) = fn für 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 können leicht in iterative Methoden transformiert werden.
M. Goedicke – Programmierung WiSe 2020/2021 25
© paluno