MyLeoNes™

Rekursion: Ein Problem mit kleineren Versionen von sich selbst lösen — Technik, 14–17 Jahre

Rekursion lässt ein Programm eine Idee wiederholen, indem es sich für einen kleineren Fall selbst aufruft. Es muss auch wissen, wann es aufhören soll, sonst endet der Vorgang nie.

Eine kleinere Version desselben Problems

Stell dir Schachteln vor, die ineinanderliegen: In jeder steckt eine kleinere, bis die letzte leer ist. Ein rekursives Programm arbeitet ähnlich und löst jedes Mal eine kleinere Version seiner Aufgabe. Es braucht einen Basisfall mit direkter Antwort.

Warum Rekursion verwenden?

Manche Probleme sind bereits verzweigt oder verschachtelt: Ordner enthalten Ordner, Webseiten verweisen auf weitere Seiten und Stammbäume teilen sich in Äste. Rekursion passt zu dieser Form und kann klarer sein als eine lange Liste von Sonderfällen.

Beispiel: Fakultät

Um 4! zu berechnen, setzen wir 1! = 1 und verwenden n! = n × (n−1)!. Also wird 4! zu 4 × 3!, dann zu 4 × 3 × 2! und schließlich zu 4 × 3 × 2 × 1! = 24. Der Basisfall 1! beendet die Kette.

Der fehlende Stopp

Ein häufiger Fehler ist, den Selbstaufruf zu schreiben, aber den Basisfall zu vergessen, oder die Eingabe so wenig zu verändern, dass er nie erreicht wird. Das ist verständlich, weil der wiederholte Schritt wie die Hauptidee wirkt. Das Ergebnis ist oft ein Stack Overflow: zu viele offene Aufrufe.

Wo sie vorkommt

Dateimanager können in Ordnern suchen, die weitere Ordner enthalten, und Zeichenprogramme können verzweigte Formen wie Bäume oder Schneeflocken erzeugen. Solche Aufgaben sind verschachtelt, daher beschreibt Rekursion sie natürlich. Sie ist aber nicht immer schneller; eine Schleife kann weniger Speicher brauchen.

Weiter erkunden

Andere Sprachen

MyLeoNes™ wird geladen…