Informatik
Startseite > Unterricht > Algorithmen und Datenstrukturen


Rekursion

Manche Aufgaben haben die Eigenart, dass sie sich auf eine einfachere Version ihrer selbst zurückführen lassen. Um eine solche Aufgabe zu lösen, "läuft" man solange über die einfacheren Stadien zurück, bis ein Anfang erreicht ist, der unmittelbar lösbar ist. Von diesem Rekursionsanfang aus wird dann die Lösung der ursprünglichen Aufgabe aufgebaut.

Beispiel 1: Gezähltes Händeschütteln

Definition: Eine Prozedur oder Funktion heißt rekursiv, wenn sie sich in ihrem Anweisungsteil selbst aufruft.

Rekursion tritt auch im täglichen Leben in Erscheinung; sie lässt sich als Wiederholung durch Schachtelung kennzeichnen. Es gibt Geschichten innerhalb von Geschichten, Filme innerhalb von Filmen, Gemälde innerhalb von Gemälden usw.

Beispiel 2: Morse-Alphabet (Finonacci-Folge)

Wenn nur ein rekursiver Aufruf stattfindet, spricht man von linearer Rekursion, andernfalls von Baumrekursion.

Beispiel 3: Sierpinski-Dreieck