Rekursion
Was versteht man unter Rekursion in der Informatik?
ErklÀrung: 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.
Jede rekursive Funktion benoetigt mindestens einen Basisfall, um die Rekursion zu beenden.
ErklÀrung: Richtig. Ohne Basisfall wuerde sich die Funktion unendlich oft selbst aufrufen, was zu einem Stapeluebelauf (StackOverflowError) fuehrt. Der Basisfall ist die Abbruchbedingung der Rekursion.
Der ___ ist die Bedingung in einer rekursiven Funktion, bei der kein weiterer rekursiver Aufruf stattfindet.
ErklÀrung: Der Basisfall (auch Rekursionsanker) beendet die Rekursion. Beispiel: Bei der Fakultaet ist der Basisfall n = 0, denn 0! = 1. Ohne Basisfall entsteht eine Endlosrekursion.
Wie lautet die rekursive Definition der Fakultaet n! ?
ErklÀrung: 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.
Berechne rekursiv: 5! (Fakultaet von 5).
ErklÀrung: 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).
Wenn eine rekursive Funktion keinen Basisfall hat, kommt es zu einem ___, weil der Aufrufstapel ueberlaeuft.
ErklÀrung: Jeder Funktionsaufruf belegt Speicher auf dem Call-Stack. Ohne Basisfall wachsen die Aufrufe unbegrenzt, bis der Speicher erschoepft ist und ein StackOverflowError auftritt.
Welcher Code zeigt indirekte Rekursion?
ErklĂ€rung: 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.
Ordne die Schritte der rekursiven Berechnung von fib(4) in der richtigen Reihenfolge (Fibonacci):
ErklÀrung: 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.
Jede rekursive Funktion kann auch iterativ (mit Schleifen) formuliert werden.
ErklÀrung: 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.
Wie oft wird die Funktion fib() bei der naiven rekursiven Berechnung von fib(5) insgesamt aufgerufen (inklusive des ersten Aufrufs fib(5))?
ErklÀrung: 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.
Die Technik, bei der Zwischenergebnisse rekursiver Aufrufe gespeichert werden, um Mehrfachberechnungen zu vermeiden, heisst ___.
ErklÀrung: 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.
Welcher der folgenden Algorithmen nutzt typischerweise Rekursion?
ErklÀrung: 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.
Ordne die Phasen des Divide-and-Conquer-Prinzips in die richtige Reihenfolge:
ErklÀrung: Divide-and-Conquer ist ein rekursives Entwurfsmuster: Erst teilen (Divide), dann rekursiv loesen (Conquer), dann zusammenfuegen (Combine). Beispiele: Mergesort, Quicksort, binaere Suche.
Die Fibonacci-Folge beginnt mit fib(1)=1, fib(2)=1. Berechne fib(7).
ErklÀrung: 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.
Beim Divide-and-Conquer-Prinzip wird ein Problem in kleinere ___ zerlegt, die rekursiv geloest werden.
ErklÀrung: Divide-and-Conquer zerlegt ein grosses Problem in kleinere Teilprobleme gleicher Struktur. Diese werden rekursiv geloest. Die Teilergebnisse werden dann zum Gesamtergebnis kombiniert.
Rekursive Algorithmen sind immer effizienter als ihre iterativen Entsprechungen.
ErklÀrung: Falsch. Rekursion verbraucht durch die Funktionsaufrufe zusaetzlichen Stapelspeicher und kann bei naiver Implementierung (z. B. Fibonacci) exponentiell langsam sein. Iterative Loesungen sind oft speichereffizienter.
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:
ErklÀrung: 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.
Was versteht man unter Endrekursion (Tail Recursion)?
ErklÀrung: 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.
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)?
ErklÀrung: 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.
Die Tuerme von ___ sind ein klassisches Beispiel fuer ein Problem, das elegant mit Rekursion geloest werden kann.
ErklÀrung: 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.