Rekursion und Backtracking
Einführung
Manche Probleme lassen sich elegant lösen, indem eine Funktion sich selbst aufruft. Dieses Prinzip heißt Rekursion und hilft dabei, komplexe Aufgaben in kleinere, ähnliche Teilprobleme zu zerlegen.Backtracking geht noch einen Schritt weiter: Dabei werden mögliche Lösungen systematisch ausprobiert und bei einer Sackgasse wieder verworfen. So kann man zum Beispiel Rätsel, Labyrinthe oder Belegungsprobleme lösen.
Begriffe
- Rekursionsaufruf
- Abbruchbedingung
- Stapel
- Backtracking
- Teilproblem