Filter:
01
Code
Aufbau einer rekursiven Methode
→ klicken zum Umdrehen
Antwort
if (einfachster Fall) return …;return … f(kleiner) …;erst Abbruchbedingung, dann Rekursionsschritt
02
Code
dosen(n)
→ klicken zum Umdrehen
Antwort
return n + dosen(n - 1);Abbruch: n == 0 liefert 0
03
Code
fakultaet(n)
→ klicken zum Umdrehen
Antwort
return n * fakultaet(n - 1);Abbruch: n <= 1 liefert 1
04
Formel
Aufrufe von fib(n)
→ klicken zum Umdrehen
Antwort
\(A(n) = 1 + A(n-1) + A(n-2)\)\(A(0) = A(1) = 1\); exponentielles Wachstum
05
Code
Quersumme
→ klicken zum Umdrehen
Antwort
return n % 10 + quersumme(n / 10);Abbruch: n < 10
06
Code
Zeichenkette umkehren
→ klicken zum Umdrehen
Antwort
return umkehren(s.substring(1)) + s.charAt(0);Abbruch: s.length() <= 1
07
Code
Binäre Suche: rechts weiter
→ klicken zum Umdrehen
Antwort
return binSuche(a, x, mitte + 1, rechts);leerer Bereich links > rechts liefert −1
08
Code
Teilbereiche bei Teile und herrsche
→ klicken zum Umdrehen
Antwort
links … mitte und mitte + 1 … rechtsmitte = (links + rechts) / 2, ganzzahlig
09
Code
mergesort(a, links, rechts)
→ klicken zum Umdrehen
Antwort
if (links < rechts): beide Hälften sortieren, dann mischestabil durch a[i] <= a[j]
10
Code
quicksort(a, links, rechts)
→ klicken zum Umdrehen
Antwort
p = zerlege(…); quicksort(a, links, p - 1); quicksort(a, p + 1, rechts);Pivot an Index p steht endgültig
11
Formel
Rekursionsgleichung Mergesort
→ klicken zum Umdrehen
Antwort
\(T(n) = 2\,T\!\left(\frac{n}{2}\right) + n\)Lösung \(T(n) = n\log_2 n\)
12
Formel
Vergleiche des rekursiven Maximums
→ klicken zum Umdrehen
Antwort
\(V(n) = n - 1\)aus \(V(n) = 2V\!\left(\frac{n}{2}\right) + 1\), \(V(1) = 0\)
13
Formel
Quicksort im ungünstigsten Fall
→ klicken zum Umdrehen
Antwort
\(\frac{n(n-1)}{2}\) Vergleiche, Tiefe \(n\)z. B. sortierte Eingabe, Pivot = letztes Element
14
Formel
Tiefe von Mergesort
→ klicken zum Umdrehen
Antwort
\(\log_2 n + 1\)bei \(2n - 1\) Aufrufen insgesamt
15
Begriff
Rekursion
→ klicken zum Umdrehen
Antwort
Eine Methode löst ein Problem, indem sie sich selbst für ein kleineres Problem derselben Art aufruft.
16
Begriff
Abbruchbedingung
→ klicken zum Umdrehen
Antwort
Der einfachste Fall, der ohne Selbstaufruf beantwortet wird (Rekursionsanfang).
17
Begriff
Rekursionsschritt
→ klicken zum Umdrehen
Antwort
Selbstaufruf mit einem kleineren Problem, dessen Ergebnis weiterverarbeitet wird.
18
Begriff
Terminierung
→ klicken zum Umdrehen
Antwort
Die Rekursion endet, weil jeder Selbstaufruf der Abbruchbedingung näher kommt, ohne sie zu überspringen.
19
Begriff
Aufrufstapel
→ klicken zum Umdrehen
Antwort
Stapel der Rahmen aller offenen Aufrufe; nur der oberste arbeitet, der zuletzt begonnene endet zuerst.
20
Begriff
Rekursionstiefe
→ klicken zum Umdrehen
Antwort
Größte Zahl gleichzeitig offener Aufrufe — bestimmt den Speicher auf dem Aufrufstapel.
21
Begriff
StackOverflowError
→ klicken zum Umdrehen
Antwort
Abbruch, wenn der Aufrufstapel voll ist — bei fehlender Terminierung oder sehr großer Tiefe.
22
Begriff
Baumrekursion
→ klicken zum Umdrehen
Antwort
Mehrere Selbstaufrufe je Aufruf; die Aufrufe bilden einen Aufrufbaum, z. B. bei
fib.
23
Begriff
Endrekursion
→ klicken zum Umdrehen
Antwort
Der Selbstaufruf ist die letzte Aktion (
return f(…)); die Methode lässt sich direkt als Schleife schreiben.
24
Begriff
Hilfsparameter
→ klicken zum Umdrehen
Antwort
Zusätzlicher Parameter, der das Restproblem beschreibt, z. B. Index
i oder Grenzen links, rechts.
25
Begriff
Teile und herrsche
→ klicken zum Umdrehen
Antwort
Problem teilen, Teilprobleme rekursiv lösen, Teillösungen zusammenführen; kleine Probleme direkt lösen.
26
Begriff
Mischen
→ klicken zum Umdrehen
Antwort
Zwei sortierte Folgen zu einer sortierten verbinden: immer das kleinere Front-Element übernehmen, Rest ohne Vergleich.
27
Begriff
Pivot
→ klicken zum Umdrehen
Antwort
Vergleichselement bei Quicksort; nach dem Zerlegen stehen links nur kleinere oder gleiche, rechts nur größere Werte.
28
Begriff
In-place
→ klicken zum Umdrehen
Antwort
Sortieren innerhalb der Reihung ohne Hilfsreihung — Quicksort ja, Mergesort nein.
29
Begriff
Stabilität
→ klicken zum Umdrehen
Antwort
Gleiche Werte behalten ihre Reihenfolge: Mergesort ist stabil, Quicksort nicht.
30
Begriff
n · log₂ n
→ klicken zum Umdrehen
Antwort
Wachstum von Mergesort (und Quicksort im Mittel): doppelte Datenmenge → etwas mehr als doppelte Arbeit.
Keine Karten in dieser Auswahl.
Geh den Stapel dreimal durch: erst alle Karten, dann nur Code und Formeln, zuletzt nur die ungelernten. Schreib bei Code-Karten die Zeile auf einen Zettel, bevor du umdrehst — und verfolge bei jeder rekursiven Methode einen kleinen Aufruf, etwa mit \(n = 3\).