Was kann man mit "Rekursion" in Java machen?

...komplette Frage anzeigen

3 Antworten

Ganz hervorragend sinnvoll mit Rekursion formulieren lassen sich solche Algorithmen, die etwas in einem hierarchischen Baum abarbeiten und nach dem Teile-und-herrsche-Prinzip arbeiten. Weil die Struktur eines Baumes VOM PRINZIP HER an jeder Stelle gleich aussieht.

Wenn man einen Baum also an seinem Wurzelknoten in zwei Teile zerlegt, hat man zwei nach gleicher Methode strukturierte Teilbäume, die man einfach wieder in den Algorithmus hineinstecken kann. WENN die Aufgabenstellung ein solches Teilen zuläßt.

Das "hervorragend" für Bäume hat einen tieferen Sinn: Wenn man linear aufgebaute Datenstrukturen größeren Umfangs hat, führt die rekursive Abarbeitung zu einer erheblichen Verlangsamung und einem gravierenden Anstieg des Ressourcenverbrauchs. Für lineare Strukturen ist Rekursion also zwar anwendbar, aber unsinnig.

Eine ungünstige Anwendung des Rekursionsprinzips kann auch schon vorliegen, wenn man zwar einen Baum vor sich hat, der aber nur wenig verzweigt, also letztlich doch eher eine lineare Datenstruktur ist. Bei (zumindest alten Versionen von) PHP gibt es einen Angriffsvektor, der auf dem fehlerhaften, extrem ressourcenfressenden und dabei nicht speicherüberwachten ABBAU von solcherart linearisiert geschachtelten Parameter-Arrays beruht - wenn man "vergißt", entsprechende Einschränkungen in der Serverkonfiguration zu setzen. Das wäre das prominenteste Beispiel einer unsinnigen Rekursionsanwendung, die zwar für den einen einzelnen Programmierer der Array-Behandlung in der PHP-Engine mal eine einzelne Arbeitsersparnis gebracht hatte, aber für hunderttausende Administratoren auf der Welt über Jahre hinweg Ärger (von den Virenopfern unter den Endanwendern gar nicht erst zu reden!).

Noch ein Zusatz: Rekursion bietet sich bei allem an, was man analog dem Beweis der vollständigen Induktion (das war glaube ich Klasse 9 oder 10) so zerlegen kann, daß man einen Ausschnitt des Systems recht einfach in einer Funktion formulieren kann, während das Gesamtsystem aus einer in sich geschachtelten Wiederholung dieses Ausschnitts besteht.

Also: Wer aus der Schule das Prinzip der vollständigen Induktion (noch oder schon) kennt, sollte sich die Angelegenheit gut vorstellen können.

Jede rekursiv formulierte Funktion kann aber auch in einer nicht rekursiven Variante formuliert werden. Wenn man recht viel Aufwand in die Entdröselung einer solchen Rekursion stecken muß, worunter die Übersichtlichkeit und/oder Wartbarkeit/Änderbarkeit leidet, ist die Rekursion vorzuziehen. Die entdröselte Variante ist aber meist schneller, so daß sich das in manchen Fällen lohnen kann.

0

Rekursion ist was teuflisch feines. Es gibt Algorithmen, die lassen sich wesentlich einfacher rekursiv schreiben, als mit einer normalen Schleife. Allerdings sollte man die Abbruchbedingung gut im Auge behalten. Wobei... Sonden sind auch schon wegen einer falschen for-Schleife abgestürtzt :).

In funktionalen Sprachen ist Rekursion oft sogar ein essentieller Bestandteil der Sprache, und sogar mit Syntactic Sugar einfach zu erzeugen/erkennen.

tatsächlich gibt es in manchen funktionalen Sprachen gar keine Iteration, sondern NUR Rekursion (z.B. Scheme).

0

Du kannst eine sich selbst aufrufende Methode schreiben. Das vereinfacht es z.B., wenn Du in einem Baum durch alle Knoten navigieren musst. Aber es gibt auch viele andere Anwendungsfälle.

Was möchtest Du wissen?