Rückblick

Rekursion ist der Punkt, an dem viele aussteigen – nicht weil sie schwer wäre, sondern weil sie ungewohnt ist. Die Prüfung, ob du sie beherrschst, ist einfach: Kannst du zu einem Problem den Basisfall und den Rekursionsschritt angeben? Alles andere folgt daraus.

Das kann ich jetzt

Ich kann eine rekursive Methode lesen und ihre Aufrufe von Hand nachvollziehen. (3.1)
Ich kann zu einem Problem Basisfall und Rekursionsschritt angeben. (3.1)
Ich kann erklären, warum eine fehlende Abbruchbedingung das Programm zum Absturz bringt. (3.1)
Ich kann das Prinzip Teilen und Herrschen an einem Beispiel erläutern. (3.2)
Ich kann Backtracking als systematisches Ausprobieren mit Zurücknehmen beschreiben. (3.3)

Aufgabe 3 gehört zum Leistungskurs.

Gemischte Aufgaben

Aufgabe 1: Aufrufe zählen

int fib(int pN) {
    if (pN <= 1) {
        return pN;
    }
    return fib(pN - 1) + fib(pN - 2);
}

a) Zeichne den vollständigen Aufrufbaum für fib(5) auf Papier.

b) Wie viele Aufrufe von fib sind das insgesamt? Zähle im Baum nach.

c) Wie oft wird dabei fib(2) berechnet? Was fällt dir auf?

d) Zähle im Programm unten mit, wie viele Aufrufe fib(10), fib(15) und fib(20) brauchen. Beschreib das Wachstum.

e) Warum ist diese Fassung trotz ihrer Eleganz eine schlechte Lösung? Was müsste man ändern?

Tipp zu a)

Die Wurzel ist fib(5). Sie hat zwei Kinder: fib(4) und fib(3). Zeichne so weiter, bis nur noch fib(1) und fib(0) an den Blättern stehen – die rufen nichts mehr auf.

Lösung. Erfrage das Passwort bei deiner Lehrkraft.

Aufgabe 2: Rekursiv formulieren

Gib für jede Aufgabe Basisfall und Rekursionsschritt in Worten an und schreib dann die Methode.

a) int summe(int[] pWerte, int pIndex) – die Summe aller Werte ab pIndex.

b) String umgekehrt(String pText) – der Text rückwärts.

c) int potenz(int pBasis, int pExponent) – die Potenz, ohne Math.pow.

d) Für welche dieser drei Aufgaben ist eine Schleife die bessere Lösung? Begründe.

Tipp: Immer dieselben zwei Fragen

Wann ist es trivial? Das ist der Basisfall – beim leeren Rest, beim einzelnen Zeichen, beim Exponenten 0.
Wie komme ich einen Schritt näher heran? Ein Element weniger, ein Zeichen weniger, ein Exponent weniger.

Fehlt Punkt 1, läuft die Rekursion endlos und das Programm bricht mit einem Überlauf des Aufrufstapels ab.

Lösung. Erfrage das Passwort bei deiner Lehrkraft.

Aufgabe 3: Zwei Strategien unterscheiden (LK)

a) Beschreib Teilen und Herrschen in drei Schritten – so allgemein, dass die Beschreibung auf Mergesort und auf die binäre Suche passt.

b) Warum ist die binäre Suche nur auf sortierten Daten möglich? Was ginge verloren, wenn die Daten unsortiert wären?

c) Beschreib das Vorgehen beim Backtracking in eigenen Worten. Welcher Schritt kommt darin vor, den es bei Teilen und Herrschen nicht gibt?

d) Ordne zu: Labyrinth durchsuchen, Zahlenfolge sortieren, Sudoku lösen, in einem Telefonbuch nachschlagen, alle Wege eines Damenproblems finden.

e) Beim Backtracking spricht man vom „Beschneiden" des Suchbaums. Erkläre, was damit gemeint ist und warum es den Unterschied zwischen „läuft" und „läuft nie fertig" ausmachen kann.

Lösung. Erfrage das Passwort bei deiner Lehrkraft.

Selbsttest

1. Was gehört zwingend zu jeder rekursiven Methode?

{c1{!ein Basisfall, in dem nicht weiter aufgerufen wird}}

{c1{!ein Schritt, der dem Basisfall näher kommt}}

{c1{eine Schleife}}

{c1{ein Feld als Parameter}}

{h{Zwei Bestandteile sind unverzichtbar – die anderen beiden kommen vor, sind aber nicht nötig.}} {H{Richtig.}}

2. Was passiert, wenn der Basisfall fehlt?

{r1{Die Methode gibt null zurück.}}

{r1{!Die Aufrufe hören nicht auf, bis der Aufrufstapel überläuft und das Programm abbricht.}}

{r1{Der Übersetzer meldet einen Fehler.}}

{r1{Die Methode wird einmal ausgeführt.}}

{h{Jeder Aufruf legt etwas auf einen Stapel, der nicht unbegrenzt ist.}} {H{Richtig – und gemeldet wird es erst zur Laufzeit.}}

3. Wie viele Aufrufe braucht die naive Fibonacci-Rekursion für n gleich 5?

{z{15}}

{h{Zeichne den Baum und zähle die Knoten.}} {H{Richtig – und für n gleich 20 sind es schon fast 22 000.}}

4. Warum ist die naive Fibonacci-Rekursion ineffizient?

{r2{Weil Rekursion grundsätzlich langsam ist.}}

{r2{!Weil dieselben Teilergebnisse immer wieder neu berechnet werden.}}

{r2{Weil sie zu viel Speicher braucht.}}

{r2{Weil sie falsche Ergebnisse liefert.}}

{h{Sieh dir im Aufrufbaum an, wie oft fib von 2 vorkommt.}} {H{Richtig.}}

5. Welche drei Schritte kennzeichnen Teilen und Herrschen?

{S1{das Problem in kleinere Teile derselben Art zerlegen}}

{S1{die Teile rekursiv lösen}}

{S1{die Teillösungen zur Gesamtlösung zusammenfügen}}

{h{Der Name nennt die ersten beiden Schritte schon.}} {H{Richtig – bei der binären Suche entfällt der dritte, weil nur eine Hälfte weiterverfolgt wird.}}

6. Welcher Schritt gehört zum Backtracking, nicht aber zu Teilen und Herrschen?

{r3{das Zerlegen des Problems}}

{r3{!das Zurücknehmen eines Schrittes, der in eine Sackgasse führt}}

{r3{der rekursive Aufruf}}

{r3{das Zusammenfügen der Teillösungen}}

{h{Der Name sagt es: zurück auf der Spur.}} {H{Richtig.}}

7. Wozu dient das Beschneiden des Suchbaums beim Backtracking?

{r4{Es macht die Lösung kürzer.}}

{r4{!Teilbäume, in denen keine Lösung liegen kann, werden gar nicht erst betreten.}}

{r4{Es sortiert die Möglichkeiten.}}

{r4{Es verhindert Endlosschleifen.}}

{h{Beim Damenproblem: Wozu weitersuchen, wenn zwei Damen sich schon bedrohen?}} {H{Richtig – das entscheidet über Sekunden oder vergebliches Warten.}}