Selbsttest — Wo stehe ich?

1.1  Was gehört zu jeder terminierenden rekursiven Methode?

1.2  dosen(n) liefert 0 für n = 0, sonst n + dosen(n − 1). Welchen Wert hat dosen(4)?

1.3  Wie viele Aufrufe entstehen bei dosen(4)?

1.4  f(n) liefert 0 für n == 0, sonst 1 + f(n − 2). Was passiert bei f(5)?

1.5  Warum muss die Abbruchbedingung vor dem Selbstaufruf geprüft werden?

1.6  Welche Fehlermeldung erzeugt eine Rekursion, die nicht endet?

1.7  Welche Definition ist rekursiv?

2.1  Was liegt in einem Rahmen auf dem Aufrufstapel?

2.2  fakultaet(4) mit Abbruch bei n ≤ 1: Wie groß ist die Rekursionstiefe?

2.3  Welcher Aufruf wird beim Aufstieg als erster beendet?

2.4  p(n) gibt n aus, ruft p(n − 1) auf und gibt danach n aus (für n > 0). Was liefert p(2)?

2.5  Wie viele Aufrufe braucht fib(4) mit Abbruch bei n ≤ 1?

2.6  Was unterscheidet Baumrekursion von linearer Rekursion?

2.7  In welcher Reihenfolge durchläuft Java den Aufrufbaum von fib(n − 1) + fib(n − 2)?

3.1  Was wird bei der Umformung einer Schleife in eine Rekursion aus der Schleifenvariablen?

3.2  Wann heißt eine Methode endrekursiv?

3.3  Wie wächst die Zahl der Aufrufe der baumrekursiven fib(n)?

3.4  Wie viele Rahmen braucht die iterative Summe einer Reihung mit 1000 Elementen?

3.5  Welche Aussage ist richtig?

3.6  Warum ist fibIter(40) viel schneller als fib(40)?

4.1  quersumme(n) liefert n für n < 10, sonst n % 10 + quersumme(n / 10). Was ergibt quersumme(503)?

4.2  Wozu dient ein Hilfsparameter wie i in maximum(a, i)?

4.3  Was liefert s.substring(1) für s = "Rekursion"?

4.4  umkehren(s) = umkehren(s.substring(1)) + s.charAt(0). Was liefert umkehren("Tor")?

4.5  Welcher Aufruf prüft in istPalindrom den Rest ohne beide Randzeichen?

4.6  Rekursive binäre Suche: Wann endet sie ohne Treffer?

4.7  Wie viele Elemente sieht die binäre Suche bei 1000 sortierten Werten höchstens an?

5.1  Welche drei Schritte hat Teile und herrsche?

5.2  Wie viele Vergleiche braucht das rekursive Maximum für n Elemente?

5.3  Wo steckt bei Mergesort die Arbeit?

5.4  Wie viele Vergleiche braucht das Mischen der Hälften 2, 7 und 3, 9?

5.5  Wo steht das Pivot nach zerlege?

5.6  Welche Aufrufe folgen bei Quicksort auf p = zerlege(a, links, rechts)?

5.7  Welches Verfahren ist stabil?

6.1  Wie viele Vergleiche braucht Mergesort höchstens für n = 1024?

6.2  Quicksort (Pivot = letztes Element) erhält sortierte Daten. Was gilt?

6.3  Wie ändert sich die Rekursionstiefe von Mergesort, wenn n verdoppelt wird?

6.4  Welchen Zusatzspeicher braucht Mergesort?

6.5  Welches Verfahren ist bei fast sortierten 50 Namen am schnellsten?

6.6  Wie viele Aufrufe von mergesort gibt es bei n = 16 insgesamt?