Teile und herrsche
Bei einem Teile-und-herrsche-Ansatz wird das eigentliche – in seiner Gesamtheit – als zu schwierig erscheinende Problem so lange rekursiv in kleinere und einfachere Teilprobleme zerlegt, bis diese gelöst ("beherrschbar") sind. Anschließend wird aus diesen Teillösungen eine Lösung für das Gesamtproblem (re-)konstruiert.
Auch das Vorgehen zur Lösung des Turms von Hanoi aus dem Rekursionsabschnitt verwendet dieses Prinzip: Zunächst erscheint es sehr komplex, einen hohen Turm aus vielen Scheiben zu versetzen - man überlegt sich also, wie ein Turm aus einer Scheibe versetzt werden kann und löst das komplexe Problem rekursiv, indem man höhere Türme auf diesen Basisfall zurückführt.
Das Teile-und-herrsche-Verfahren ist kein simpler Algorithmus, den du einfach auf eine Aufgabe anwendest. Es ist vielmehr eine Art, über eine Problemstellung nachzudenken.
Wir betrachten einige weitere Beispiele, um das Prinzip besser zu verstehen.