MINT üben

Rekursion und Iteration

Dreißig Übungen zum Übersetzen zwischen Schleife und Rekursion und zum Vergleich des Aufwands.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Dreißig Ü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: Jeder Aufruf legt einen Rahmen an.
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 und fibIter 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.
Eigenschaftfib (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.