Rekursive Algorithmen

Viele Probleme können mit dem Top-down oder dem Bottom-up-Ansatz gelöst werden, indem eine Probleminstanz in mehrere kleinere Probleminstanzen aufgeteilt wird und dann die kleineren Probleminstanzen einzeln gelöst werden. Am Ende werden die Lösungen der kleineren Probleminstanzen wieder zusammengeführt, um das ursprüngliche Problem zu lösen. Diese Problemlösestrategie wird auch in der Mathematik und in der Informatik angewendet, um gewisse Probleme zu lösen. Die genannte Strategie möchten wir nun ein wenig abändern, und zwar so, dass es sich nicht nur um eine Reduktion der Problemgrösse (Grösse der Probleminstanz) handelt, sondern dass kleinere Probleminstanzen in gleicher Weise mit demselben Verfahren gelöst werden können. Dadurch entsteht die Rekursion. Aus diesem Grund ergibt sich folgende Leitidee: Die Methode der Rekursion soll auf verschiedene Problemstellungen angewendet werden und es soll darüber hinaus untersucht werden, welche Probleme nur oder anders gesagt wesentlich einfacher mittels Rekursion gelöst werden können.