Programmierung Übung 7 Goedicke
Programmierung: Übung 7 – Rekursion Aufgabe 1
1.
Als Rekursion bezeichnet man den Vorgang, dass Regeln auf ein Produkt, das sie selbst erzeugt haben, von neuem angewandt werden. Hierdurch entstehen potenziell unendliche Schleifen. Unter Rekursion versteht man also in der Programmierung ein Verfahren, bei dem sich eine Methode selbst aufruft, sodass, ähnlich einer Endlosschleife, ein potentiell unendlicher Programmablauf entsteht. In Java wird das Prinzip umgesetzt, indem bei jedem rekursiven Aufruf wird dabei eine neue Instanz der jeweiligen Methode gestartet bis eine Abbruchbedingung eintritt. Das Problem wird durch den Aufruf immer kleinerer Teilprobleme in einen Programmcode zerlegt, und nach Lösung des kleinsten Teilproblems wird das nächstgrößere gelöst und so weiter bis das Gesamtproblem gelöst ist. Einen Stack kann man sich als Bücherstapel vorstellen. Die erste Methode 3! ruft die zweite Methode 2! auf, diese ruft Methode 1! auf; in diesem Moment ist der Stack bei 3, daraufhin baut er sich wieder ab, da Methode für Methode einen return-Wert bekommt.
2.
Eine rekursiver Methodenrumpf besteht mindestens aus Endbedingung (Determinierungsbedingung, die die Rekursion
beendet) und rekursivem Ausdruck.
3.
A ruft B an und fragt nach einer Telefonnummer; B kennt die Telefonnummer nicht, weiß aber, dass C sie kennt; B ruft C an und fragt nach der Telefonnummer; C hat ihr Notizbuch bei D vergessen; C ruft D an und fragt nach der Telefonnummer; D teilt C, C teilt B und B teilt A die Telefonnummer mit.
Verpackungen, auf deren Etikett die gleiche Verpackung dargestellt ist
Fernsehbild, das einen Ansager zeigt, neben der ein Fernseher steht, auf der man das Fernsehbild und damit den Ansager wiedersehen kann
Gegenstand, der zwischen zwei parallele Spiegel gehalten wird, erscheint vervielfacht.
Es war einmal ein Mann, der hatte 7 Kinder, und die Kinder sprachen: „Vater, erzähl uns eine Geschichte“. Und der Vater begann: „Es war einmal ein Mann, der hatte 7 Kinder, und die Kinder sprachen: „Vater, erzähl uns eine Geschichte“. Und der Vater begann: „Es war einmal ein Mann, der hatte 7 Kinder, und die Kinder sprachen: …
public class RekursionAufgabe3 {
public static void tagevorderKlausur(int tage) {
System.out.println(“Prokrastination”); if(tage == 0) {
System.out.println(“Game Over”); } else {
tagevorderKlausur(tage – 1); }
}
public static void main(String[] args) { tagevorderKlausur(2);
} }
4.
Rekursion ist für das Durchlaufen eines Binärbaums besonders geeignet, weil er an jedem Knoten höchstens zwei weitere Optionen hat. So, muss man immer wieder dasselbe machen, da es immer wieder kleine Binärbäume sind, die einen großen ergeben. Würde man das iterativ durchlaufen, bräuchte man einen Pointer.
Seite 1 von 3
Programmierung Übung 7 Goedicke Aufgabe 2
public class Aufgabe2 {
public static void main (String[] args) {
System.out.println(multiplyFromStartToEnd(1,3)); }
public static int multiplyFromStartToEnd(int start, int end) { if (start == end) {
return end; } else {
} }
}
Aufgabe 3
a)
→binärer Suchbaum
b)
Der Baum hat eine Höhe von 4 (= Anzahl Kanten).
c)
mindestens: Höhe + 1 = 5 höchstens: 24+1 – 1 = 31
return start * multiplyFromStartToEnd(
++start
, end);
Terminierungsblock
Rekursion
start++ geht nicht, weil Inkrementation erst auf dem „Rückweg“ passieren; Problem: Wir kommen nicht zurück, wenn wir
die Endbedingung nicht erreichen.
start + 1 würde funktionieren
Seite 2 von 3
Programmierung Übung 7 Goedicke
d) (eigene Lösung)
Seite 3 von 3
Powered by TCPDF (www.tcpdf.org)