[Diskusion]: Warum überhaupt Rekursion verwenden?

_fux_

_fux_

0
hi leute,

ohne großartige worte:

warum sollte ich rekursion überhaupt in meinen Code benutzen, wenn ich doch iterative Lösungen basteln kann? Das problem ist ja, das Rekursion zwar sehr bequem zu programmieren ist, jedoch ist es doch sicher, das Rekursion teilweise recht langsam sein kann, je nach dem wie schlecht mans programmiert.

Ich hatte mal ein Projekt programmiert, das 1 mil. werte sortieren sollte. Ich hatte eine Rekursive und Iterative Lösung gecodet! Die Iterative Lösung war um einiges schneller.

wie denkt ihr darüber? es gibt bei uns nämlich ne Prof, die "rekursions"fan ist. Ich jedoch bin absolut gar nicht fan davon, da es ja einfach oft eine einfache, aber ineffiziente lösung ist.

wie seht ihr das?
wollte mal andere meinungen hören/lesen, die mitstudenten die ich habe, den scheints teilweise egal zu sein (warum studiert man dann info? Oo)
 
Hallo,
ich frag mich echt, was du gegen Rekursion hast.
Gut, die Standardbeispiele (z.B. Fakultät) sind unsinnig, viele Probleme lassen sich damit sehr elegant lösen und übersichtlich lösen und sind nicht viel langsamer als iterative Lösungen.

Versuch z.B. Quicksort iterativ zu lösen, oder gib einen Baum/Graphen (z.B. Verzeichnisbaum) mal iterativ aus, oder allgemein die Arbeit mit Bäumen, rekursive Lösungen sind einfach sehr schön anzugucken und auch leicht zu verstehen.
Dort musst du dann auch auf einen Stack zurückgreifen, was die dein Geschwindigkeitsgewinn stark beeinträchtigt.

In vielen Fällen spielt Performance nicht so die starke Rolle, ob man nun einen Verzeichnisbaum iterativ oder rekursiv ausgibt, ist relativ egal, nur ist die rekursive Variante deutlich übersichtlicher, lässt sich besser überprüfen und auch schneller geschrieben.

Es kommt eben stark auf die Tiefe drauf an, wenn die maximale Tiefe zum Beispiel nur 10 ist, sind rekursive Lösungen nicht merklich langsamer.
 
Soso, dann zähle mir bitte die Vorteile einer iterativen Lösung bei:
Baumoperation(Balansierung,suche), Backtracking, Parsing (Grammatikdefenitionen sind auch rekursiv :) )und einfach mal die üblichen Divide &Conqueer Lösungen ;)
Manche iterativen Lösungen sind nur "simulierte" Rekursionen oder haben nur einen einzigen Vorteil - sie legen keine Rücksprungadresse auf dem Stack ab (sonst aber vom Speicherverbrauch gleich).

Weiterhin spielt Rekursion eine wichtige Rolle bei Algorithmenbeweisen. Da kann man durch vollständige Induktion die Richtigkeit eines Sortieralgorithmus beweisen und den dann notfalls iterativ machen (man muss nur noch schlüssig nachweisen, dass die iterative Vorgehensweise äquivalent ist). Es spielt auch eine große Rolle bei Berechenbarkeitsbeweisen - da es aber sehr trocken war, habe ich damals nicht aufgepasst :)

Auch kann man das einfach als Prototyping verwenden - eine schnell geschriebene Lösung, die nicht schnell sein muss, aber die Richtigkeit der Idee zeigt/prüft.

Edit: zu lange in alten Sachen gewühlt :)
 
Oder auch AI kann ohne Rekursion nicht wirklich sinnvoll erstellt werden. Auch Methoden wie MTD-f sind ohne Rekursion nicht möglich.
 
@_fux_:
Mal eine kleine Programmieraufgabe für dich:
Schreibe ein Programm, welches eine Ordnerstruktur mit Dateien auflistet. (Alternativ könnte man auch in JS das DOM auflisten).
Bedingung: Verwende dabei keine Rekursion!

Wie würdest du das lösen? Hab bis jetzt keine iterative Lösung für dieses Problem gefunden.
 
Wie jede rekursive Funktion lässt sich die Endrekursion mittels Iteration darstellen.
Zum Vergrößern anklicken....
Von wikipedia

Das ist ja schön und gut, aber das könne man auch gerade ausschreiben nennen...
Dann wird die Datei oder was auch immer riesig und bei einer Rekursion von tiefe n hätte man immer noch ein Problem.

Die Baumstruktur ist schon ein gutes Beispiel. Ein anderes wären auch logische Spiel wie z.B. Schach. Da müsstest du mit Iteration alle Stellungen, die überhaupt jemals möglich sind ausprobieren und also etwas zu viele Stellungen. Ohne ungültige Stellungen wären das (16!^2*64!*2)/(8!^2*2^6*32!^2) ca. 7e+81 Möglichkeiten nach den ersten Bewegungen. Man kann ca 99.9% ungültige abzählen, aber das sind dann immer noch ziemlich viele ;) (ich hoffe die Rechnung stimmt in etwa).
 
Original von :::Lük:::
Wie würdest du das lösen? Hab bis jetzt keine iterative Lösung für dieses Problem gefunden.
Zum Vergrößern anklicken....

indem man die Unsortierte Liste der Elemente in die Richtige Reihenfolge sortiert sodass bei einer Verzeichnisstruktur dann z.B. da steht: "/", "/bin", "unterverz. 1 von bin", "unterverz. 2 von bin", "/boot", "unterverz. 1 von boot", ......; außerdem hat jedes Element noch eine variable, die die Anzahl an parents angibt, sodass man in der endgültigen ausgabe entsprechend einrücken kann:
Code: 
/               parentcount: 0
 /bin           parentcount: 1
  /untervz1     parentcount: 2
  /untervz2     parentcount: 2
 /boot          parentcount: 1
  /untervz1     parentcount: 2

alternativ kann man auch von anfang an dafür sorgen, dass man eine geordnete Liste hat, das nimmt einem auch nochmal Arbeit ab die man später haben würde.


Außerdem wollte ich auch noch anmerken, dass im Linux-Kernel aus eben dem Grund des Geschwindigkeitsvorteils keine Rekursion verwendet wird (bzw. es wird empfohlen, dass keine verwendet werden sollte)
 
Hab zwar nicht alles gelesen, aber Baum-Operationen sind auch sehr schön und übersichtlich mit Hilfe des Visitor Patterns zu lösen.

Grundsätzlich stimmt ich aber zu, dass Rekursion sehr oft den Code sehr viel übersichtlicher macht. Wenn man jetzt nicht gerade 1 Mio Durchgänge hat und jedes mal n neues Objekt erzeugt, das dann im RAM vergammel, erstellt ist das auch kein Problem.
 
@Serow: das glaube ich eher nicht. Es regelt nämlich keineswegs wie man konkret durch den Baum traversiert ;).
 
Außerdem wollte ich auch noch anmerken, dass im Linux-Kernel aus eben dem Grund des Geschwindigkeitsvorteils keine Rekursion verwendet wird (bzw. es wird empfohlen, dass keine verwendet werden sollte)
Zum Vergrößern anklicken....
Wie immer kommt es hier auf den Anwendungsbereich drauf an - und wie immer versuche ich mal wieder, diesen Geschwindigkeitsfaschismus auszurotten.

1. Bei elementaren, häufig verwendeten Funktionen, wie sie der Kernel bereitstellt, ist das durchaus sinnvoll, eben nicht auf Rekursion zu setzen - aber das ist keine Entscheidung, die man mal auf die schnelle trifft und dann sofort eine iterative Lösung präsentiert. Meistens schleichen sich da mehr als genug Fehler ein, der Code wird unverständlich usw, das ganze macht viel Arbeit.

2. Um Optimierungen bzw Ressourcen / Geschwindigkeit kümmert man sich, *falls* man ein Problem damit hat. Es scheint immer mehr in Mode zu sein, wild & sinnlos im Voraus rumzuoptimieren, was nur dazu führt, dass kein Mensch den Code lesen kann, er dadurch jede Menge Fehler enthält (die alles andere als trivial zu debuggen sein können) usw.

Effektiv handelt man sich damit wesentlich mehr Ärger ein, als erstmal eine möglicherweise langsame / ressourcenfressende, aber einfache und va korrekte Implementation hinzukriegen, auf deren Interface basierend dann den Rest der Applikation (die durchaus testbar ist, denn man hat ja eine korrekte Implementation der Rekursion), und später einfach die Rekursion zu ersetzen. Auch in Hinblick auf Unit-Tests sind einfache Lösungen zu bevorzugen, während man die Tests schreibt.
Das ist ja schön und gut, aber das könne man auch gerade ausschreiben nennen... Dann wird die Datei oder was auch immer riesig und bei einer Rekursion von tiefe n hätte man immer noch ein Problem.
Zum Vergrößern anklicken....
Ich verstehe jetzt deinen Text nicht, habe aber das Gefühl, du verstehst tail recursion nicht :)
Dabei geht es eher darum, dass z.b. ein optimierender Compiler eine endrekursive Funktion durch eine äquivalente iterative Funktion ersetzt (gerade das geht nämlich bei Endrekursion sehr einfach). Damit lässt sich im Source eine rekursive Lösung halten, während die Binary von den Vorteilen einer iterativen Ausführung profitiert.
 
Bis jetzt hat niemand nur von tail recursion gesprochen und recursion beinhaltet weit mehr als das...
Ausserdem, auch enrekursive Funktionen lassen sich leider nicht immer durch Iteration vereinfachen. Es gibt viele rekursive Funktionen, wo einiges erst während der Rekursion bekannt wird oder während der rekursion bekannt wird, dass einige Äste des Rekursionsbaum z.B. gar nicht benutzt werden müssen.
 
ich wollte mir mal die tage auch mal die freien quake engines anschauen und durchforsten, ob ich da rekursive methoden entdecken kann. ich vermute ja eher nicht.

und warum sollte mich es kümmern, das jemand mein quellcode versteht? mit ner doku ist das meistens ja schon getan, dann braucht mal halt noch schlaue köpfe die das nachvollziehen :-)

interesante ansichtsweisen hier, aber ich glaube ich werde mich nicht von meiner "anti-rekursions" ansicht abwenden ;) das heißt nicht zwangsweise auch, das ich ichs nicht benutztn werde*g


mein projekt zwischendurch ist es ja, einen optimierten binär baum zu schreiben, der 100% funktioniert, selber rotiert ect...
und alles iterativ -> was natürlich viel aufwand bedeutet, aber ich denke es ist die sache wert....gute erfahrung halt
 
Hallo,
Original von CDW
Manche iterativen Lösungen sind nur "simulierte" Rekursionen oder haben nur einen einzigen Vorteil - sie legen keine Rücksprungadresse auf dem Stack ab (sonst aber vom Speicherverbrauch gleich).
Zum Vergrößern anklicken....

Wie schon erwähnt, muss man für manche iterative Lösungen einen Stack anwenden.

Das Problem ist, eigentlich jede Programmiersprache unterstützt Rekursion, aber nicht jede Sprache bietet eine einfache Methode für einen Stack.
Nimmt man beispielsweise PHP, dort muss man dann noch zusätzlich einen Stack implementieren.

Beispielsweise dieses Programm:
PHP: 
<?php

function ausgabeDir($path, $prefix = "") {
$handle = opendir($path);
while (false !== ($file = readdir($handle))) {
       if($file == "." or $file == "..")
             continue;

        if(is_file($file))
          echo $prefix.$file."<br>";
       elseif(is_dir($file))
          ausgabeDir($path."/".$file, $prefix." ");
    }

closedir($handle);
}

echo "<pre>";
aufgabeDir(".");
?>

Hier müsste man ansonsten einen Stack implementieren, was unter PHP vermutlich langsamer wäre als die Rekursion.

Wie gesagt, Rekursion ist unter so gut wie jeder Prog.sprache vorhanden, deswegen ist es ganz praktisch damit Algorithmen zu beschreiben.
 
@fux:
Dann achte mal bei den Engines auf die implementierung der BSP-Trees ;)
Wenn Du Lust hat, kannst Du Dir auch eine Open Source Datenbank zur Gemüte führen (diese nutzen in der Regel B-Trees) sowie paar Dateisystemimplementierungen (wiederum B-Trees Variationen).
Falls es eine iterative Implementierung gibt, dann wohl in diesen Anwendungen.

Allerdings schätze ich hier mal einfach rum: ein 32-facher rekursiver Aufruf einer Baumtraversierungsprozedur tut nicht wirklich weh. Genau genommen ist es für moderne Computer nix - aber damit können wir in einem balancierten BinBaum ein Element aus 4Mrd finden. Eventuelle Perfomanceprobleme werden allerdings wegen Speicherzugriff auftreten, sobald man soviele Werte nicht mehr im RAM cachen kann. Dann wird man sich eher Gedanken um eine anständige Organisation der Daten machen, als um die 32*(meinertwegen 100 Bytes) Rekursionsoverhead der Such/Lösch/usw Funktionen ;)
 
und warum sollte mich es kümmern, das jemand mein quellcode versteht?
Zum Vergrößern anklicken....
1. Du solltest ihn selbst verstehen, und einfacherer Code ist einfacher zu verstehen, als schiweriger :)
2. Wenn du alleiniger Entwickler bist, mag das noch soweit korrekt sein, aber sobald mehrere Leute an einem Projekt sitzen, sieht die Sache evtl. anders aus - von anderen Benutzer ganz zu schweigen. Versteh mich nicht falsch, wenn die Performance ein kritischer Punkt ist, macht eine Optimierung auf Kosten der Les- und Wartbarkeit durchaus Sinn - sonst aber nicht.
3. Komplizierter Code führt a) zu mehr Fehlern, b) zu schwieriger zu findenden / beseitigenden Fehlern.

Um Mal ein anderes Beispiel zu bringen: Ich bastle gerade an einer Lib, die mir Menüs bauen soll - ganze einfache Baumstruktur, bei der jedes Element einen Namen hat und die Blätter ein Objekt, das sie zurückgeben (Stichwort: Composite Pattern). Das ganze garniert mit Konsolenausgabe, Konversion zu allen möglichen GUI-Menüs, Menüdefinitionen in XML usw.

Die Tiefe eines Baumes, durch die sich ein Mensch durchklicken will, ist relativ gering, insofern kann ich Performance-Probleme und Stack Overflows ausschließen (außer jemand baut Kreise, ist auch schon vorgekommen :))
Macht hier also eine iterative Implementation Sinn? Ich denke nicht. Meine rekursive Lösung ist ein 4-Zeiler, die auch jeder auf Anhieb versteht. Und selbst bei so etwas einfachem ist Korrektheit alles andere als eine triviale Eigenschaft, allein schon durch die kaum überschaubare Menge an Exceptions, die man durchgeschliffen bekommt.

Die Sun-JVM wirft bei mir übrigens gerade nach 11580 rekursiven Aufrufen einen StackOverflow, in dem Sinne ist da also schon ordentlich Platz. Probleme wird man da wohl erst, wie CDW schon sagte, woanders bekommen.

Und das Fazit, wie immer: Es kommt wohl drauf an, was man machen will.
 
Original von t3rr0r.bYt3
Die Sun-JVM wirft bei mir übrigens gerade nach 11580 rekursiven Aufrufen einen StackOverflow, in dem Sinne ist da also schon ordentlich Platz. Probleme wird man da wohl erst, wie CDW schon sagte, woanders bekommen.
Zum Vergrößern anklicken....

Ich habe neulich in C++ im "operator=" einer klasse dummerweise (war irgendwie um 4 uhr morgens) "(*this) = übergebenesobj;" geschrieben, bevor da der Stack überlaufen ist, hats auch ca. 100000 Aufrufe gegeben.
Heutzutage macht der funktionsaufrufoverhead also wohl nicht mehr allzuviel aus, ich werde aber trotzdem, wenn ich eine _gute_ iterative Methode zur lösung des Problems finde, diese vorziehen :)
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben