Rekursion

Recursion

Informatik Klasse 11 20 Aufgaben
AlgorithmenRekursionKerncurriculum

Eine rekursive Funktion ruft sich selbst auf — jeweils mit einem kleineren Problem, bis ein Basisfall ohne weiteren Aufruf lösbar ist (Fakultät, Fibonacci). Die dokumentierte Fehlvorstellung ist das „Schleifenmodell" (Kahney): Der rekursive Aufruf springe zurück an den Anfang. Tatsächlich entsteht pro Aufruf ein eigener Rahmen mit eigenen Parametern auf dem Aufrufstapel, und die Ergebnisse laufen beim Abbau zurück — genau das zeigt ein Aufrufbaum.

Voraussetzungen (2)

Funktionen und Datenflüsse
Klasse 9
›
Programme Schritt für Schritt verfolgen
Klasse 9
›

Ermöglicht (1)

Datenstrukturen
Klasse 11
›
Leicht
Multiple Choice #1 20s ▶ Testen

Was versteht man unter Rekursion in der Informatik?

  • ○ Eine Schleife, die rueckwaerts zaehlt
  • ● Eine Funktion, die sich selbst aufruft, um ein Problem zu loesen
  • ○ Eine Methode zur Datenbankabfrage
  • ○ Ein Sortierverfahren fuer Arrays
Rekursion bedeutet, dass eine Funktion sich selbst aufruft. Das Problem wird dabei in kleinere Teilprobleme zerlegt, bis ein Basisfall erreicht wird, der ohne weiteren Aufruf geloest werden kann.
Wahr / Falsch #2 15s ▶ Testen

Jede rekursive Funktion benoetigt mindestens einen Basisfall, um die Rekursion zu beenden.

✓ Wahr
Richtig. Ohne Basisfall wuerde sich die Funktion unendlich oft selbst aufrufen, was zu einem Stapeluebelauf (StackOverflowError) fuehrt. Der Basisfall ist die Abbruchbedingung der Rekursion.
Lückentext #3 15s ▶ Testen

Der ___ ist die Bedingung in einer rekursiven Funktion, bei der kein weiterer rekursiver Aufruf stattfindet.

✓ Antwort: Basisfall
Der Basisfall (auch Rekursionsanker) beendet die Rekursion. Beispiel: Bei der Fakultaet ist der Basisfall n = 0, denn 0! = 1. Ohne Basisfall entsteht eine Endlosrekursion.
Multiple Choice #4 20s ▶ Testen

Wie lautet die rekursive Definition der Fakultaet n! ?

  • ○ n! = n + (n-1)!
  • ● n! = n * (n-1)! mit 0! = 1
  • ○ n! = n * n mit 1! = 1
  • ○ n! = (n-1) * (n-2)!
Die Fakultaet ist rekursiv definiert: n! = n * (n-1)! mit dem Basisfall 0! = 1. Beispiel: 4! = 4 * 3! = 4 * 3 * 2! = 4 * 3 * 2 * 1! = 4 * 3 * 2 * 1 = 24.
Zahleneingabe #5 20s ▶ Testen

Berechne rekursiv: 5! (Fakultaet von 5).

✓ Antwort: 120
5! = 5 * 4! = 5 * 4 * 3! = 5 * 4 * 3 * 2! = 5 * 4 * 3 * 2 * 1! = 5 * 4 * 3 * 2 * 1 = 120. Der Basisfall ist 1! = 1 (oder 0! = 1).
Lückentext #6 15s ▶ Testen

Wenn eine rekursive Funktion keinen Basisfall hat, kommt es zu einem ___, weil der Aufrufstapel ueberlaeuft.

✓ Antwort: StackOverflow
Jeder Funktionsaufruf belegt Speicher auf dem Call-Stack. Ohne Basisfall wachsen die Aufrufe unbegrenzt, bis der Speicher erschoepft ist und ein StackOverflowError auftritt.
Lückentext #7 15s ▶ Testen

Beim Divide-and-Conquer-Prinzip wird ein Problem in kleinere ___ zerlegt, die rekursiv geloest werden.

✓ Antwort: Teilprobleme
Divide-and-Conquer zerlegt ein grosses Problem in kleinere Teilprobleme gleicher Struktur. Diese werden rekursiv geloest. Die Teilergebnisse werden dann zum Gesamtergebnis kombiniert.
Mittel
Multiple Choice #1 20s ▶ Testen

Welcher Code zeigt indirekte Rekursion?

  • ● gerade(n) ruft ungerade(n−1) auf, ungerade(n) ruft gerade(n−1) auf
  • ○ f(n) ruft f(n−1) auf
  • ○ f(n) ruft g(n) auf, g(n) gibt n + 1 zurück
Bei indirekter Rekursion ruft Funktion A eine Funktion B auf, die wiederum A aufruft (gerade ↔ ungerade). Ruft sich f selbst auf, ist das direkte Rekursion. Ruft f nur g auf, ohne dass g zurück zu f führt, liegt gar keine Rekursion vor. Beide Rekursionsformen brauchen Basisfälle.
Sortieren #2 30s ▶ Testen

Ordne die Schritte der rekursiven Berechnung von fib(4) in der richtigen Reihenfolge (Fibonacci):

✓ Antwort: fib(4) ruft fib(3) und fib(2) auf, fib(3) ruft fib(2) und fib(1) auf, fib(2) gibt 1 zurueck (Basisfall), fib(1) gibt 1 zurueck (Basisfall), Ergebnisse werden aufsummiert: fib(4) = 3
Die Fibonacci-Folge ist rekursiv definiert: fib(n) = fib(n-1) + fib(n-2) mit fib(1) = fib(2) = 1. Der Aufrufbaum verzweigt sich, bis die Basisfaelle erreicht sind.
Wahr / Falsch #3 15s ▶ Testen

Jede rekursive Funktion kann auch iterativ (mit Schleifen) formuliert werden.

✓ Wahr
Richtig. Rekursion und Iteration sind gleichmaechtig. Jede Rekursion laesst sich in eine Schleife umwandeln (ggf. mit einem expliziten Stapel). Umgekehrt kann jede Schleife rekursiv formuliert werden.
Zahleneingabe #4 30s ▶ Testen

Wie oft wird die Funktion fib() bei der naiven rekursiven Berechnung von fib(5) insgesamt aufgerufen (inklusive des ersten Aufrufs fib(5))?

✓ Antwort: 15
Der Aufrufbaum: fib(5) ruft fib(4) und fib(3). fib(4) ruft fib(3) und fib(2). fib(3) erscheint mehrfach. Insgesamt: fib(5)=1, fib(4)=1, fib(3)=2, fib(2)=3, fib(1)=5, fib(0)=3 => 15 Aufrufe.
Lückentext #5 20s ▶ Testen

Die Technik, bei der Zwischenergebnisse rekursiver Aufrufe gespeichert werden, um Mehrfachberechnungen zu vermeiden, heisst ___.

✓ Antwort: Memoisation
Memoisation speichert bereits berechnete Ergebnisse (z. B. in einer Tabelle). Bei der Fibonacci-Folge reduziert sie die Anzahl der Aufrufe von exponentiell auf linear, weil fib(k) nur einmal berechnet wird.
Multiple Choice #6 20s ▶ Testen

Welcher der folgenden Algorithmen nutzt typischerweise Rekursion?

  • ○ Lineare Suche
  • ● Mergesort
  • ○ Bubble Sort
  • ○ Insertion Sort
Mergesort ist ein klassisches Divide-and-Conquer-Verfahren: Das Array wird rekursiv in Haelften geteilt, bis nur noch Einzelelemente uebrig sind, die dann sortiert zusammengefuegt werden.
Sortieren #7 20s ▶ Testen

Ordne die Phasen des Divide-and-Conquer-Prinzips in die richtige Reihenfolge:

✓ Antwort: Divide: Problem in Teilprobleme zerlegen, Conquer: Teilprobleme rekursiv loesen, Combine: Teilergebnisse zusammenfuegen
Divide-and-Conquer ist ein rekursives Entwurfsmuster: Erst teilen (Divide), dann rekursiv loesen (Conquer), dann zusammenfuegen (Combine). Beispiele: Mergesort, Quicksort, binaere Suche.
Zahleneingabe #8 25s ▶ Testen

Die Fibonacci-Folge beginnt mit fib(1)=1, fib(2)=1. Berechne fib(7).

✓ Antwort: 13
fib(3)=2, fib(4)=3, fib(5)=5, fib(6)=8, fib(7)=13. Jeder Wert ist die Summe der zwei vorherigen: 8 + 5 = 13.
Wahr / Falsch #9 15s ▶ Testen

Rekursive Algorithmen sind immer effizienter als ihre iterativen Entsprechungen.

✓ Falsch
Falsch. Rekursion verbraucht durch die Funktionsaufrufe zusaetzlichen Stapelspeicher und kann bei naiver Implementierung (z. B. Fibonacci) exponentiell langsam sein. Iterative Loesungen sind oft speichereffizienter.
Schwer
Sortieren #1 30s ▶ Testen

Ordne die rekursiven Aufrufe bei der binaeren Suche nach dem Wert 7 im sortierten Array [1,3,5,7,9,11] in der richtigen Reihenfolge:

✓ Antwort: Pruefe mittleres Element: 5 (zu klein), Suche in rechter Haelfte [7,9,11], Pruefe mittleres Element: 9 (zu gross), Suche in linker Haelfte [7], Element 7 gefunden (Basisfall)
Die binaere Suche halbiert den Suchbereich bei jedem Schritt. Das ist ein rekursiver Ansatz: Vergleiche mit der Mitte, dann suche rekursiv in der passenden Haelfte.
Multiple Choice #2 25s ▶ Testen

Was versteht man unter Endrekursion (Tail Recursion)?

  • ○ Eine Rekursion, die am Ende des Programms steht
  • ● Eine Rekursion, bei der der rekursive Aufruf die letzte Operation der Funktion ist
  • ○ Eine Rekursion mit genau einem Basisfall
  • ○ Eine Rekursion, die keine Parameter hat
Bei Endrekursion ist der rekursive Aufruf die allerletzte Anweisung. Der Compiler kann dies in eine Schleife optimieren (Tail-Call-Optimization), sodass kein zusaetzlicher Stapelspeicher benoetigt wird.
Zahleneingabe #3 20s ▶ Testen

Eine rekursive Funktion berechnet die Summe von 1 bis n: summe(n) = n + summe(n-1) mit summe(0) = 0. Wie viele rekursive Aufrufe finden bei summe(8) statt (ohne den initialen Aufruf)?

✓ Antwort: 8
summe(8) ruft summe(7) auf, summe(7) ruft summe(6) auf, ..., summe(1) ruft summe(0) auf. Das sind 8 weitere Aufrufe, bis der Basisfall summe(0) = 0 erreicht wird.
Lückentext #4 20s ▶ Testen

Die Tuerme von ___ sind ein klassisches Beispiel fuer ein Problem, das elegant mit Rekursion geloest werden kann.

✓ Antwort: Hanoi
Die Tuerme von Hanoi: n Scheiben muessen von Stab A nach Stab C verschoben werden (ueber Stab B). Rekursiver Algorithmus: Verschiebe n-1 Scheiben nach B, die groesste nach C, dann n-1 von B nach C. Basisfall: 1 Scheibe direkt verschieben.