Informatik Algorithmen – Rekursion und Backtracking
Karteikarten zum Thema „Informatik“ · 14 Karten · von atrio. Beispiele: Was ist Rekursion in der Informatik? · Welche zwei Bestandteile hat jede rekursive Fu…
Karten
14 KartenWas ist Rekursion in der Informatik?
Rückseite
Eine Funktion ruft sich selbst auf, um ein Problem in kleinere Teilprobleme gleicher Struktur zu zerlegen.
Welche zwei Bestandteile hat jede rekursive Funktion?
Rückseite
Ein Basisfall (Abbruchbedingung) und ein Rekursionsschritt, der das Problem verkleinert und die Funktion erneut aufruft.
Was passiert, wenn ein Basisfall fehlt?
Rückseite
Die Rekursion endet nie, der Call Stack läuft über und verursacht einen Stack Overflow.
Was zeigt ein Rekursionsbaum?
Rückseite
Er visualisiert alle Funktionsaufrufe, deren Parameter und Rückgabewerte, und macht redundanten Berechnungen sichtbar.
Was ist Tail-Rekursion (Endrekursion)?
Rückseite
Der rekursive Aufruf ist die letzte Operation der Funktion, sodass Compiler sie in eine Schleife umwandeln können.
Wie vermeidet Memoization redundante Berechnungen?
Rückseite
Ergebnisse bereits gelöster Teilprobleme werden gespeichert und bei erneutem Bedarf direkt zurückgegeben, statt neu berechnet zu werden.
Was charakterisiert Backtracking als algorithmisches Paradigma?
Rückseite
Es baut Lösungskandidaten schrittweise auf und verwirft (backtrackt) Teilwege, sobald sie die Constraints verletzen.
Worin unterscheidet sich Backtracking von brutaler Suche?
Rückseite
Backtracking prüft Constraints früh und bricht ungültige Pfade ab, Brute-Force testet alle Kombinationen vollständig.
Nenne ein klassisches Backtracking-Problem.
Rückseite
Das N-Damen-Problem: n Damen auf einem n×n-Schachbrett so platzieren, dass keine zwei sich schlagen.
Welche drei Phasen durchläuft ein Backtracking-Algorithmus?
Rückseite
Der Algorithmus wählt einen Kandidaten, prüft Constraints und rekursiert weiter oder setzt die Wahl zurück.
Was bedeutet Pruning beim Backtracking?
Rückseite
Frühes Abschneiden von Suchzweigen, die keine gültige Lösung mehr führen können, um Laufzeit zu reduzieren.
Wie berechnet man die Fakultät n! rekursiv?
Rückseite
Die Fakultät wird definiert als 0! = 1 und für n > 0 als n! = n × (n-1)!.
Warum ist die naive Fibonacci-Rekursion ineffizient?
Rückseite
Die naive Fibonacci-Rekursion berechnet gleiche Teilprobleme mehrfach, wodurch die Laufzeit exponentiell statt linear wächst.
Wann ist Iteration der Rekursion vorzuziehen?
Rückseite
Bei einfachen linearen Abläufen, begrenztem Stack-Speicher oder wenn Tail-Rekursion nicht vom Compiler optimiert wird.