MyLeoNes™

Rekursion — Informatik, 14–17 Jahre

Wie man ein Problem löst, indem man eine kleinere Version desselben Problems erzeugt, mit einem klaren Punkt, an dem der Vorgang endet.

Idee

Rekursion bedeutet, dass eine Funktion eine Aufgabe löst, indem sie sich selbst mit einer kleineren oder einfacheren Eingabe aufruft. Sie braucht außerdem einen Basisfall, der direkt beantwortet werden kann. Jeder Aufruf führt dorthin, wie eine kleinere Schachtel in einer Schachtel bis zur letzten.

Warum das wichtig ist

Manche Probleme enthalten kleinere Kopien von sich selbst. Ordner enthalten Ordner, Stammbäume haben Verzweigungen, und ein Labyrinth kann kleinere Bereiche zum Erkunden enthalten. Rekursion beschreibt solche Formen natürlich, weil dieselben Anweisungen wiederverwendet werden, statt Code für jede Tiefe zu schreiben.

Durchgerechnetes Beispiel

Um 4 Fakultät zu berechnen, setzen wir fact(1)=1 als Basisfall. Dann gilt fact(4)=4×fact(3), fact(3)=3×fact(2) und fact(2)=2×fact(1). Von unten nach oben eingesetzt ergibt das 2×1=2, 3×2=6 und 4×6=24, also 4!=24.

Typischer Stolperstein

Ein verständlicher Fehler ist, den Selbstaufruf zu schreiben und den Basisfall oder den Schritt dorthin zu vergessen. Dann ruft sich der Code endlos weiter auf, weil der Computer nicht erraten kann, wann die Aufgabe fertig ist. Selbst mit Basisfall kann ein falscher Schritt die Eingabe vergrößern statt verkleinern.

Wo es vorkommt

Browser, Dateiverwaltung und Suchsysteme erkunden oft verschachtelte Ordner oder verknüpfte Seiten mit rekursiven Ideen. Bildprogramme können ein Bild ebenfalls in kleinere Bereiche teilen und diese weiter teilen. Rekursion ist nützlich, weil auf jeder Ebene dieselbe Aktion gilt, bis ein Bereich klein genug ist.

Weiter erkunden

Andere Sprachen

MyLeoNes™ wird geladen…