Fachkonzept
In den letzten beiden Kapiteln haben wir uns das Konzept der Rekursion anhand der Diagramme des RecursionTutors angeschaut. Fassen wir die daraus gewonnene Erkenntnis zusammen und umreißen das Konzept zunächst so:
Die Kernidee der rekursiven Lösungsstrategie ist also:
Eine Alternative Lösungsstrategie ist die Iteration, also mithilfe von Schleifen. Oft ist die rekursive Lösung allerdings kürzer, eleganter und einfacher zu verstehen.
Die zwei Bausteine der Rekursion
Rekursive Programme benötigen zum Lösen von Problemen immer zwei ganz bestimmte Bausteine:
1. Der Basisfall
Der Basisfall ist der Punkt, an dem das Problem so klein und einfach ist, dass wir die Lösung davon direkt kennen, ohne das Problem weiter verkleinern zu müssen. Das ist der Punkt, an dem die Rekursion aufhört. Ohne einen Basisfall würden wir nie fertig werden mit der Lösung eines Problems.
In unseren Beispiel sum_list wäre der Basisfall die leere Liste, also eine Liste ohne aufzusummierende Elemente. bei der quersumme wäre der Basisfall eine Zahl mit nur einer Ziffer, bei der wir nichts aufsummieren müssen. Also die jeweils kleinste Version des Problems. Zu dieser Version sagen wir auch Instanz.
2. Der Rekursionsschritt
Der Rekursionsschritt ist der Schritt, in dem wir das Problem auf eine kleinere Version desselben Problems zurückführen. Dann versuchen wir das Problem zu lösen, aber eben die kleinere Version bzw. Instanz davon. Wir starten also unsere gesamte Lösungsstrategie komplett neu, allerdings mit einer verkleinerten Version des Problems. Das machen wir, um dem Basisfall Schritt für Schritt näher zu kommen.
Die beiden Bausteine der Rekursion können wir im Diagramm des RecursionTutors schön sehen:
Mit einem Linksklick führen wir genau einen weiteren Rekursionsschritt aus. Solange der Basisfall noch nicht erreicht ist, können wir immer wieder Rekursionsschritte ausführen. Sobald der Basisfall erreicht wurde kann das ursprüngliche Problem gelöst werden.
