Rekursion

Was bedeutet „Rekursion“?

Ein Verfahren, bei dem eine Funktion sich selbst aufruft.

So verwendest du das Wort

Die Fakultät lässt sich elegant per Rekursion berechnen.

Die gleiche Aufgabe im kleineren Maßstab

Du suchst eine Datei in einem Ordner. Darin liegen Dateien und weitere Ordner, die wiederum Unterordner enthalten können. Statt für jede mögliche Tiefe eine neue Anweisung zu erfinden, kannst du dieselbe Suchregel auf jeden Unterordner anwenden. Diese Struktur passt zur Rekursion.

Der Weg durch die Ordner

Prüfe zunächst die Dateien des aktuellen Ordners. Für jeden enthaltenen Unterordner führst du anschließend dieselbe Suche aus. Hat ein Ordner keine weiteren Unterordner, gibt es dort nichts mehr auf diese Weise zu durchsuchen. Danach kehrst du zur vorherigen Ebene zurück.

Selbstbezug als Verfahren

Rekursion bezeichnet ein Vorgehen, bei dem eine Aufgabe mithilfe gleichartiger Teilaufgaben bearbeitet wird. In Programmen ruft eine Funktion dafür häufig sich selbst auf, direkt oder über andere Funktionen. Wichtig sind ein sinnvoller Übergang zu Teilproblemen und ein Fall, der ohne weiteren Aufruf bearbeitet werden kann.

Wiederholung allein genügt nicht

Eine Schleife kann dieselbe Anweisung mehrfach ausführen, ohne dass ein Selbstaufruf stattfindet. Rekursion und solche Wiederholung können ähnliche Aufgaben lösen, beschreiben aber unterschiedliche Strukturen. Fehlt ein erreichbarer Abschluss oder führt der nächste Schritt immer wieder zum selben Problem, kann das rekursive Verfahren scheitern.

Den Begriff passend verwenden

„Die Ordnerstruktur wird mithilfe von Rekursion durchsucht.“ Der Satz benennt das Verfahren, nicht dessen Geschwindigkeit. Rekursion ist nicht automatisch schneller oder verständlicher als andere Lösungen. Bei sehr vielen verschachtelten Aufrufen müssen Programme außerdem beachten, wie viel Speicher für die noch offenen Schritte benötigt wird.

Den Abschluss finden

Zeichne drei ineinanderliegende Ordner und schreibe in jeden einen Dateinamen. Verfolge die Suchregel vom äußeren bis zum innersten Ordner und zurück. Markiere, wo kein weiterer Unterordner mehr vorhanden ist. Dieser Punkt hilft dir, den Abschlussfall von der bloßen Fortsetzung des Verfahrens zu unterscheiden.