TUForMath
Abstrakt
Rekursion ist ein gängiges Konzept in der gesamten Mathematik. Man denke etwa an die Summe von n Zahlen. Intuitiv ist klar, was gemeint ist, aber eigentlich ist es die Summe von n-1 Zahlen plus die n-te Zahl. Das ganze beginnt bei n=1.
Abgesehen von solchen (wenn man so will) definitorischen Spitzfindigkeiten ist Rekursion ein mächtiges Werkzeug einerseits in Beweisführungen (hier spricht man meist von Induktion), wo man von n-1 auf n schließt, und andererseits in der Programmierung von Algorithmen. Auf beide Aspekte wird hier eingegangen. Wir diskutieren auch den Aspekt, ob bzw. wie wir als Menschen ‘rekursiv denken’.
Als Beispiel präsentieren wir einen Algorithmus für das Problem der ‘Türme von Hanoi’. Die rekursive Formulierung ist sehr einfach verständlich; dahinter versteckt sich eine ‘direkte’ Lösung, die jedoch als solche sehr umständlich zu realisieren wäre. In der Sprache der Informatik wird hier intern ein sogenannter ‘stack’ (Stapelspeicher) verwendet, in dem Zwischenergebnisse abgelegt und wieder aufgerufen werden können.
