Rekursion — Informatik, 11–13
Rekursion löst ein großes Problem, indem dieselbe Regel auf eine kleinere Version angewendet wird, bis ein einfacher Stopp erreicht ist.
Eine Regel, die sich selbst aufruft
Bei der Rekursion bearbeitet eine Anweisung einen Teil und bittet dann dieselbe Anweisung, einen kleineren Teil zu bearbeiten. Sie muss außerdem wissen, wann sie aufhören soll: Das ist der Basisfall. Ein Ast zeigt die Idee: Jeder Ast teilt sich in kleinere Äste, aber der kleinste Zweig teilt sich nicht weiter.
Warum Rekursion verwenden?
Manche Dinge bestehen aus kleineren Kopien derselben Art: Ordner enthalten Ordner, Stammbäume verzweigen sich und Karten enthalten Regionen in Regionen. Eine lange Liste einzelner Anweisungen wäre schwer zu schreiben und zu ändern. Rekursion entstand, um solche verschachtelten Strukturen mit einer klaren Regel zu beschreiben, statt ähnlichen Code zu wiederholen.
Rückwärts zählen
Verwende eine Regel namens count(n): Wenn n gleich 0 ist, stoppe; sonst gib n aus und rufe count(n−1) auf. Starte mit count(3). Sie gibt 3 aus, ruft dann count(2) auf, gibt 2 aus und ruft count(1) auf. Dort erscheint 1 und count(0) wird aufgerufen; der Basisfall stoppt, also lautet die Ausgabe 3, 2, 1.
Den Stopp vergessen
Eine rekursive Regel kann elegant wirken, deshalb vergisst man leicht, einen Basisfall zu prüfen. Das ist ein verständlicher Fehler: Es scheint, als würden die kleineren Aufgaben irgendwann von selbst verschwinden. Ohne Stopp erreicht der Wert aber vielleicht nie das Ende, und der Computer erzeugt immer mehr unfertige Aufrufe, bis der Platz ausgeht oder ein Fehler erscheint.
Ordner und verzweigte Formen
Dateiprogramme können einen Ordner und danach jeden darin enthaltenen Ordner durchsuchen, egal wie tief sie verschachtelt sind. Zeichenprogramme verwenden Rekursion auch für verzweigte Pflanzen, schneeflockenartige Formen und Wege durch Labyrinthe. Du brauchst Rekursion nicht für jede Wiederholung; sie ist besonders nützlich, wenn jeder Teil kleinere Teile derselben Struktur enthält.
Weiter erkunden
Andere Sprachen
MyLeoNes™ wird geladen…