Zehn Übungen zum Übersetzen zwischen Schleife und Rekursion und zum Vergleich des Aufwands.
Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Zehn Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt dir sofort Rückmeldung; wenn du nicht weiterkommst, helfen die gestuften Tipps.
A1
Stimmt's? — Rekursion oder Schleife
AFB I
Gib zu jeder Aussage an, ob sie stimmt.
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.
Aussage 1 von 5
Merksatz: gleich mächtig, aber nicht gleich teuer — Rekursion bezahlt mit Stapelspeicher und Aufrufaufwand.
Ansatz: Denk an den Aufrufstapel aus 3.1.2.
Weiter: Zähle bei der Summe die Werte von i einschließlich des Abbruchfalls.
A2
Von der Schleife zur Rekursion
AFB I
Ordne jedem Teil der iterativen Summe den passenden Teil der rekursiven Fassung zu.
Klicke links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Die Schleifenbedingung beschreibt, wann weitergemacht wird, die Abbruchbedingung, wann aufgehört wird — deshalb ist die eine die Verneinung der anderen.
Ansatz: Beginne mit dem Startwert: Womit wird die rekursive Methode zum ersten Mal aufgerufen?
Weiter: Wo steckt in der rekursiven Fassung das Zwischenergebnis?
A3
Zwei Fibonacci-Methoden
AFB I
Lies aus den Quelltexten von fib (3.1.2) und fibIter (Inhaltsseite) ab, welche Eigenschaft auf welche Methode zutrifft.
Setze alle zutreffenden Kreuze — in einer Zeile können auch beide Spalten richtig sein. Enter setzt und löscht.
Eigenschaft
fib (rekursiv)
fibIter (iterativ)
braucht je offener Ebene einen eigenen Rahmen
berechnet fib(2) beim Aufruf mit n = 5 mehrfach
kommt mit den Variablen a, b, neu aus
liefert für n = 10 den Wert 55
kann bei sehr großem n einen StackOverflowError auslösen
Beide liefern dieselben Werte. Unterschiede gibt es beim Aufwand: Rahmen je Ebene und Doppelberechnungen bei fib, feste Zahl von Variablen bei fibIter.
Ansatz: Welche Methode ruft sich selbst auf?
Weiter: Eine Zeile gilt für beide Methoden.
A4
Rekursion in eine Schleife übersetzen
AFB II
binaerLaenge(n) liefert die Anzahl der Binärstellen von \(n \ge 1\). Erstelle eine gleichwertige Methode mit Schleife, indem du die Zeilen ordnest.
static int binaerLaenge(int n) {
if (n <= 1) return 1;
return 1 + binaerLaenge(n / 2);
}
Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1static int binaerLaenge(int n) {
2 int laenge = 1;
3 while (n > 1) {
4 n = n / 2; laenge++;
5 } // Ende while
6 return laenge;
7} // Ende der Methode
Die Abbruchbedingung n <= 1 wird verneint zur Schleifenbedingung n > 1; der Rückgabewert 1 des Abbruchfalls wird zum Startwert von laenge, jedes „1 +“ zu laenge++.
Ansatz: Der Wert der Abbruchbedingung wird zum Startwert der Zählvariablen.
Weiter: Die Schleife läuft, solange die Abbruchbedingung nicht gilt.
A5
Aufrufe gegen Durchläufe
AFB II
Berechne für n = 6 den Wert und den Aufwand beider Fibonacci-Methoden.
Arbeite die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
Ansatz: Nutze A(3) = 5 und A(4) = 9 aus der Herleitung in 3.1.2.
Weiter: A(n) = 1 + A(n − 1) + A(n − 2).
A6
Lineare Suche rekursiv
AFB IIMix
Die lineare Suche aus Kapitel 2 lässt sich rekursiv schreiben. Vergleiche sie mit der Schleifenfassung, indem du die Lücken füllst.
static int suche(int[] a, int x, int i) {
if (i == a.length) return -1;
if (a[i] == x) return i;
return suche(a, x, i + 1);
}
Wort anklicken, dann Lücke anklicken (oder umgekehrt) — mit Tab und Enter geht es genauso. Ein Klick auf eine gefüllte Lücke legt das Wort zurück.
Beide Fassungen brauchen im ungünstigsten Fall Vergleiche a[i] == x. Die rekursive Fassung legt dabei bis zu Rahmen auf den Stapel, die Schleife nur . Weil der Selbstaufruf die letzte Aktion ist, ist die Methode . Die Schleifenbedingung i < a.length ist die Verneinung der ersten .
Bei n Elementen gibt es Aufrufe mit i = 0 bis i = n; der letzte meldet „nicht gefunden“. Zwei Wörter bleiben übrig: log₂ n gehört zur binären Suche, baumrekursiv zu Methoden mit zwei Selbstaufrufen.
Ansatz: Zähle die Werte von i beim erfolglosen Suchen, einschließlich i = a.length.
Weiter: Nach return suche(a, x, i + 1); passiert nichts mehr.
A7
Produkt mit Fehlern
AFB II
Die rekursive Methode produkt(a, i) wurde in eine Schleife übersetzt — dabei sind Fehler entstanden. Überprüfe die Übersetzung und korrigiere die falschen Zeilen.
static int produkt(int[] a, int i) {
if (i == a.length) return 1;
return a[i] * produkt(a, i + 1);
}
Klicke die fehlerhaften Zeilen an — dann klappt ein Feld auf, in das du die richtige Zeile schreibst. Geprüft werden Auswahl und Korrekturen.
Richtige Zeile:
Richtige Zeile:
Der Abbruchfall der Rekursion liefert 1 — das ist der Startwert der Schleife; mit 0 wäre jedes Produkt 0. Die Abbruchbedingung i == a.length wird zu i < a.length; mit <= gäbe es eine ArrayIndexOutOfBoundsException.
Ansatz: Vergleiche Startwert und Bedingung mit der Abbruchbedingung der Rekursion.
Weiter: Zwei Zeilen sind falsch.
A8
Wie hoch wird der Stapel bei fib(40)?
AFB IIITrick
fib(40) erzeugt über 300 Millionen Aufrufe. Ermittle die größte Zahl von Rahmen, die dabei gleichzeitig auf dem Aufrufstapel liegen.
Überlege selbst und trage das Ergebnis ein — Enter prüft direkt.
Der längste Ast läuft fib(40) → fib(39) → … → fib(1): 40 Rahmen. Die vielen Aufrufe entstehen nacheinander — jeder Teilbaum ist fertig und abgebaut, bevor der nächste beginnt. Deshalb scheitert fib(40) an der Zeit, nicht am Stapel.
Ansatz: Gesucht ist die Rekursionstiefe, nicht die Zahl der Aufrufe.
Weiter: Folge immer dem Aufruf fib(n - 1) bis zum Abbruchfall.
A9
Rekursiv — gute Idee?
AFB III
Beurteile, wie gut sich eine rekursive Lösung für die jeweilige Aufgabe eignet.
Schätze jede Zeile auf der Skala von ungeeignet (1) bis gut geeignet (5) ein. Mit der Tastatur: Tab zur Zeile, ←/→ zwischen den Stufen, Enter setzt.
1 = ungeeignet5 = gut geeignet
fib(50) mit zwei Selbstaufrufen je Aufruf
Türme von Hanoi mit 10 Scheiben
Summe einer Reihung mit 10 Millionen Einträgen, ein Aufruf je Element
Fakultät von 15
binäre Suche in einer sortierten Reihung
fib(50) braucht Milliarden Aufrufe, die lange Summe sprengt den Stapel. Hanoi ist rekursiv natürlich gedacht, iterativ mühsam. Fakultät und binäre Suche sind rekursiv unproblematisch (Tiefe 15 bzw. etwa log₂ n), iterativ aber genauso einfach.
Ansatz: Frage bei jeder Aufgabe: Wie tief wird der Stapel, und wiederholen sich Teilprobleme?
Weiter: Wie natürlich ist die rekursive Formulierung im Vergleich zur Schleife?
A10
Fibonacci endrekursiv
AFB III
Die Idee von fibIter — zwei Werte wandern mit — lässt sich auch rekursiv umsetzen: fibEnd(n, a, b) wird mit fibEnd(n, 0, 1) gestartet und braucht nur n + 1 Aufrufe. Entwirf die Methode aus den Bausteinen.
Setze den Bauplan von oben nach unten zusammen. Ein Klick legt den Baustein auf den nächsten freien Platz, ein Klick im Bauplan legt ihn zurück. Enter funktioniert genauso.
Die Parameter a und b übernehmen die Rolle der Schleifenvariablen: Aus (a, b) wird (b, a + b). Weil der Selbstaufruf die letzte Aktion ist, ist die Methode endrekursiv — und rechnet schon beim Abstieg.
Ansatz: Vergleiche mit der Schleife in fibIter: Was wird aus a, was aus b?
Weiter: Nach n Schritten steht der gesuchte Wert in a.
