Rekursion vermeiden... Wieso?
-
Sorry, ich finde da die Antwort auf eine Frage nicht. Woran machst Du fest ob ein Algorithmus (oder meinetwegen auch ein Prozess) iterativ oder rekursiv ist?
Wenn Du oben sagst, dass es Sachen gibt, die rekursiv machbar sind, aber iterativ nicht, dann mußt Du doch irgendeinen harten Begriff in der Hand haben, mit dem Du solche Aussagen tätigen kannst. Nur danach frage ich. -- Offensichtlich verbindest Du nämlich mit iterativ/rekursiv andere Begrifflichkeiten als ich. Deswegen komme ich ja auch zu einer anderen Aussage.
-
Wenn der benoetigte Speicher fuer Zwischenergebnisse im Vergleich zur Ein- bzw. Ausgabe waechst.
-
knivil schrieb:
Wenn der benoetigte Speicher fuer Zwischenergebnisse im Vergleich zur Ein- bzw. Ausgabe waechst.
Okay, verstehe. Das halte ich für keine besonders glückliche Definition, aber das steht ja auf nem anderen Blatt.
edit: nochmal zur Klärung, das heißt ein Algorithmus, der sagen wir quadratischen Speicher (quadratisch in der Eingabegröße) benötigt um als Ergebnis eine Zahl zu berechnen wäre automatisch rekursiv?
-
Gegenfrage: Ist die Auswertung der Helperfunktion rekursiv oder eher iterativ. Ich finde schon, dass die Auswertung hier an eine for-Schleife mit Hilfsvariable erinnert. Andererseits kann auch Rekursion herbeigefuehrt werden, ohne das eine Funktion sich selbst aufruft. Siehe http://en.wikipedia.org/wiki/Fixed_point_combinator unter Y combinator.
edit: nochmal zur Klärung, das heißt ein Algorithmus, der sagen wir quadratischen Speicher (quadratisch in der Eingabegröße) benötigt um als Ergebnis eine Zahl zu berechnen wäre automatisch rekursiv?
Nenne doch mal ein Beispiel. Jedoch beachte das nicht nur die Eingabe von Bedeutung ist, sondern auch die Ausgabe. Wenn ich Elemente mit bestimmten Eigenschaften in einem Array suche, dann brauche ich auch Speicher im Sinne der Ausgabe. Das zaehlt natuerlich nicht. Genau wie ich fuer 120! natuerlich mehr Speicher brauche als fuer 120. Es geht mir nur um das zusaetzliche an Speicher. Das ist ja auch der Grund dafuer, warum auf Rekursion meist verzichtet wird.
-
Es gibt viele Algorithmen deren Bedarf an temporärem Speicher mit der Grösse der Eingabe steigt (ob linear oder logarithmisch oder sonstwie is je egal).
Deswegen würde ich aber noch lange nicht alle solchen Algorithmen als "rekursiv" bezeichnen. Sind sie auch nicht.Rekursiv ist etwas, wo ich als Teil der Berechnung, exakt die selbe Berechnung für kleinere Teilmengen durchführe, bis ich eine bestimmte Schwelle erreicht habe (wie z.B. dass die Teilmengen auf ein einziges Element zusammengeschrumpft ist).
Ob ich das jetzt mit rekursiven Funktionen mache, oder einem selbst verwalteten Hilfs-Stack, ist eigentlich egal.
Es geht hier aber soweit ich es verstanden habe nicht um rekursive Algorithmen vs. nicht rekursive Algorithmen, sondern um rekursive Funktionen vs. nicht rekursive Funktionen.
-
knivil schrieb:
Das ist ja auch der Grund dafuer, warum auf Rekursion meist verzichtet wird.
Meinst du nicht eher das ist meist der Grund, warum auf Rekursion verzichtet wird (WENN auf Rekursion verzichtet wird)?
So wie du das formuliert hast, würde es bedeuten, dass kaum jemals irgendwer Rekursion verwendet, weil man eben "meist darauf verzeichtet".
-
Ishildur schrieb:
Nun glaube ich, das Ganze zu verstehen. Man könnte für das TreeTraversal ein simples dynamisch alloziertes c-array als Stack benutzen und tauscht, 65'536 Funktionsaufrufe gegen ein einziges new und delete. Das kann IMHO doch eine menge bringen
Hardwarestack ist schneller als Softwarstack. Deswegen bost Du mit dem simulierten Stack langsamer. Ist der Baum auch noch balanciert, hat man sogar die nötige Rekursionstiefenbeschränkung.
Also gehe ich durch den AVL-Baum wohl rekursiv und durch einen Verzeichnisbaum mit simulierter Rekursion.
-
knivil schrieb:
edit: nochmal zur Klärung, das heißt ein Algorithmus, der sagen wir quadratischen Speicher (quadratisch in der Eingabegröße) benötigt um als Ergebnis eine Zahl zu berechnen wäre automatisch rekursiv?
Nenne doch mal ein Beispiel. Jedoch beachte das nicht nur die Eingabe von Bedeutung ist, sondern auch die Ausgabe.
Okay, ein doofes Beispiel, aber eines das meine Bedenken gut zeigt. Eingabe sind n Punkte in einem vector und eine Zahl x. Zu beantworten ist die Frage, ob es ein Punktpaar gibt, dessen Abstand größer ist als x.
Meine Implementierung macht nun folgendes: Sie legt eine nxn großes Feld an und schreibt da die paarweisen Abstände rein. Anschließend wird das Maximum des Feldes ausgerechnet und dieses mit x verglichen.
Eingabe hat Größe O(n), Ausgabe O(1), Speicherbedarf O(n^2). Nach meinem Geschmack ist das zwar ne dämliche Implementierung, aber rekursiv ist sie imo nicht.
-
hustbaer schrieb:
Rekursiv ist etwas, wo ich als Teil der Berechnung, exakt die selbe Berechnung für kleinere Teilmengen durchführe, bis ich eine bestimmte Schwelle erreicht habe (wie z.B. dass die Teilmengen auf ein einziges Element zusammengeschrumpft ist).
das sehe ich genauso.
Es geht hier aber soweit ich es verstanden habe nicht um rekursive Algorithmen vs. nicht rekursive Algorithmen, sondern um rekursive Funktionen vs. nicht rekursive Funktionen.
Ja, so sah das ursprünglich für mich mal aus. Daher auch der Einwand mit der Äquivalenz von rekursiver und while-Berechenbarkeit.
-
knivil hat seine Definition mit ziemlicher Sicherheit (evtl. indirekt) aus SICP:
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2
-
Bashar schrieb:
knivil hat seine Definition mit ziemlicher Sicherheit (evtl. indirekt) aus SICP:
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2Ja, das war meine Grundlage. Ich haette auch darauf verlinkt, aber konnte es irgendwie finden.
@Jester: Da stimmme ich dir zu. Dem entgegenhalten wuerde ich, dass es eine eher ungluecklich implementiert ist. Man kann immer irgendwelchen Bloedsinn machen. Auch hat hustbaer auf das Problem aufmerksam gemacht, aber ich weiss es nicht genau in Worte zu fassen.
-
Also ich würde sagen, etwas ist Rekursiv, wenn es sich auf sich selber bezieht.
Ob das jetzt eine Funktion, ein Datentyp oder die natürlichen Zahlen sind, ist
erstmal egal.Beschränkt man sich auf rekursive Funktionen, und möchte verstehen warum es
Leute gibt, die das vermeiden, muss man verstehen was Rekursion bedeutet.Im Computer wird ein Funktionsaufruf mithilfe von einem Stack gemacht. Dieser
wird genutzt, um:
* die Parameter an die nächste Funktion zu übergeben,
* die Rücksprungadresse der alten Funktion zu sichern,
* die Adresse des Stackframes zu sichern,
* vielleicht noch was?
Hat man jetzt eine Funktion, die sich selber aufruft, wächst mit jedem
Funktionsaufruf der Stack an. Da der Stack nicht unendlich ist, kann es sein,
dass irgendwann der Platz nicht mehr ausreicht und das Programm abstürzt.Kann man dieses Problem vermeiden? Ja, mithilfe von Tail-Rekursion.
Das bedeutet, dass der rekursive Aufruf immer die letzte Anweisung der Funktion
ist. Der Vorteil liegt darin, dass der Compiler einen solchen Funktionsaufruf
in einen "Sprung" an den Funktionsanfang auflösen kann.Dass bedeutet nun, dass der Stack nicht anwächst und so auch nicht überlaufen
kann.Ich denke daher, Rekursion zu verbieten ist ganz sicher der falsche Ansatz.
Denn man verbietet ein sehr elegantes Abstraktionswerkzeug. Und das führt
sicher zu viel größeren Problemen.Allerdings ist es auch wichtig, dass man versteht, wann ein rekursiver Aufruf
Probleme bereiten kann.Also Rekursion nicht verbieten, sondern aufklären!
grüße,
frosch
-
Also ich würde sagen, etwas ist Rekursiv, wenn es sich auf sich selber bezieht.
Ja, aber nicht nur, wie der Y-Kombinator zeigt.
Rekursion zu verbieten ist ganz sicher der falsche Ansatz
Wer will das denn?
-
knivil schrieb:
Rekursion zu verbieten ist ganz sicher der falsche Ansatz
Wer will das denn?
Es gibt immer wieder solche Forderungen. Und es gibt immer Unternehmen, die Rekurson verbieten. Sogar große wie die Deutsche Bahn sind davor nicht gefeit.
rüdiger schrieb:
Es gibt in C und C++ keinen Weg festzustellen, ob der Stackspeicher ausreicht und es gibt keinen Weg sich von einem Stackoverflow zu retten. Daher ist Rekursion in C und C++ eine potentiell böse Sache und viele Codingguidelines verbieten die Verwendung von Rekursion.
-
Das ist "Rekursion in C und C++", was da verboten ist. In Sprachen, in denen ein Stack-Overflow genauso zuverlässig abgefangen werden kann wie eine fehlgeschlagene Speicheranforderung, ist das Argument nicht gültig.
-
knivil schrieb:
Ja, aber nicht nur, wie der Y-Kombinator zeigt.
Ein 'fixed point'-Kombinator zeigt doch nur, ob Rekursion in einem Paradigma
möglich ist.Und wenn du dir jetzt eine anonyme rekursive Funktion mittels Y-Kombinator baust
dann bezieht die sich doch trotzdem noch auf sich selbst, oder irre ich?Nur mal so aus Interesse, weil ich's mir grad nicht vorstellen kann. Kann man
Stack-Overflow's tatsächlich zuverlässig abfangen? Und falls ja, wie würde man so
etwas anstellen?grüße,
frosch03
-
mit try ... catch? Dürfte in jeder höheren Programmiersprache gehen.
-
Bashar schrieb:
mit try ... catch? Dürfte in jeder höheren Programmiersprache gehen.
Nein, ganz sicher nicht.
-
frosch03 schrieb:
Nur mal so aus Interesse, weil ich's mir grad nicht vorstellen kann. Kann man
Stack-Overflow's tatsächlich zuverlässig abfangen? Und falls ja, wie würde man so etwas anstellen?C, C++, Java und C# bieten keinen mir bekannte Mechanismus an, mit dem man einen Stack-Overflow behandeln/abfangen/... könnte.
Das OS in Zusammenarbeit mit dem Compiler kann allerdings "reine" Stack-Overflows sehrwohl zuverlässig erkennen (also welche die nicht mit "unchecked buffer" Fehlern o.Ä. kombiniert sind). Ob man den betroffenen Thread danach noch weiterverwenden kann ist eine andere Frage.
Machen tut man das mit Guard-Pages und Stack-Probes.
Dazu generiert der Compiler am Anfang jeder Funktion, die mehr als eine Page an Stack braucht, eine kleine Schleife, die im Abstand von einer Page einfach Werte vom Stack ausliest (oder schreibt - ist egal). Ausgehend vom aktuellen Stack-Pointer, und bis zum neuen Wert des Stack-Pointers. Damit ist garantiert, dass keine Page übersprungen wird.Am "Ende" des Stacks befindet sich dann eine Guard-Page, also eine Page die "not present" markiert ist. Wenn das OS im entsprechenden Trap-Handler sieht dass eine Guard-Page "getroffen" wurde, weiss es, dass das Programm einen Stack-Overflow gebaut hat.
-
Ah, dat is ja spannend... Erinnert mich jetzt gerade ein wenig an diese "Stack Canaries"
mit denen man buffer-overflow's erkennen kann.Aber sehe ich das richtig, mit dieser Erkennung rettet man nur das OS vor dem sichern
Suizid? Der Prozess der den stack-overflow verursacht hat davon erstmal wenig?Ich glaube im übrigen, dass man solche stack-overflow's garnicht allgemein im
Voraus erkennen kann. Denn irgendwie scheint mir, als käme dass der Lösung des
Halte-Problems gleich (Und dat hat ja bekanntlich noch niemand gelöst :))In jedem Fall 'ne Spannende Geschichte die ganze Thematik.
