Ablauf¶
Rekursion - Allgemein¶
Rekursion (lateinisch recurrere – ‚zurücklaufen‘) ist ein prinzipiell unendlicher Vorgang, der sich selbst als Teil enthält oder mithilfe von sich selbst definierbar ist. In der Informatik geschieht Rekursion immer dann, wenn eine Funktion sich selbst aufruft.
- Typische Anwendungen sind Divide-and-Conquer-Algorithmen und Kombinatorische Probleme
Rekursion in Python¶
Rekursion in Python erreicht man indem eine Funktion sich selbst wieder aufruft.
def rekursive_funktion():
Statement1
rekursive_funktion()
Beispiel: Fakultät¶
Die Fakultät einer Zahl ist definiert als Produkt der natürlichen Zahlen von $1$ bis $n$
def factorial_recursiv(x):
if x > 1:
return x * factorial_recursiv(x - 1)
else:
return 1
Achtung: Endlosrekursion¶
Bei rekursiven Funktionen gibt es das selbe Problem, wie bei while-Schleifen: Sie können sich (theoretisch) endlos verzweigen!
Deshalb sollte mindestens ein Pfad in der Funktion nicht rekursiv sein.
Hintergrund: Stack Overflow Fehler¶
- Der Stack ist eine Liste in der nachvollzogen wird welche Funktionen gerade aufgerufen wurden
- Damit ist bekannt, wohin man zurückkehrt, wenn eine Funktion beendet wird
- Bei endloser Rekursion, wird die Liste unendlich groß
Hintergrund: Stack Overflow Fehler¶
Der Stack ist eine Liste in der nachvollzogen wird welche Funktionen gerade aufgerufen wurden
Damit ist bekannt, wohin man zurückkehrt, wenn eine Funktion beendet wird
Bei endloser Rekursion, wird die Liste unendlich groß
Es kommt bei endloser Rekursion zu Stack-Overflow-Fehlern
Es kommt zum harten Absturz des Programmes
Heap vs Stack¶
Der Stack ist ein Speicherbereich, in dem Funktionsaufrufe und deren lokale Variablen nach dem LIFO-Prinzip (Last In First Out) verwaltet werden. Jeder neue Funktionsaufruf wird oben auf den Stack gelegt und beim Beenden wieder entfernt. Ist der Stack voll, kommt es zum StackOverflow-Fehler.
- Für Funktionsaufrufe
- LIFO-Prinzip
- Begrenzter Speicher
Als Heap bezeichnet man einen Speicherbereich, in dem Variablen verwaltet werden. Der Heap ist im Gegensatz zum Stack nicht begrenzt sondern wächst dynamisch mit dem Bedarf. Speicher im Heap wird nach dem FIFO-Prinzip (First In First Out) verwaltet und muss explizit freigegeben werden.
- Für Variablen
- FIFO-ähnlich
- Dynamisch groß (RAM)
Lesson Learned - Nacharbeit¶
- Survey (Überblick gewinnen): Blättert durch ein Thema und gewinnt einen Überblick
- Question (Fragen): Notiert euch Fragen zu Punkten die ihr nicht versteht.
- Read (Lesen): Lest eure Notizen durch; Hebt Schlüsselwörter hervor; Recherchiert zu den Fragen.
- Recite (Wiedergeben): Rekapituliert jeden Abschnitt (Inhalt, Schlüsselwörter, Zusammenhänge). Strukturiert euch die Inhalte, z.B. mit Mindmaps. Wiederholt Gelerntes mehrmals (Karteikarten).
- Review (Rückblick): Wiederholt gedanklich die wichtigsten Punkte und beantwortet eure Fragen.
Mindmap¶
- Man arbeitet von innen nach außen
- Reduziert Themen auf einzelne Begriffe
- Man entwickelt automatisch eine Struktur
- Nutzt Farben und Symbole
- Verweise zwischen Begriffen erschaffen
