Rekursion vermeiden... Wieso?

volkard

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.

Jester

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.

Jester

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.

Bashar

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

knivil

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.2

Ja, 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.

frosch03

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

knivil

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?

volkard

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.

Bashar

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.

frosch03

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

Bashar

mit try ... catch? Dürfte in jeder höheren Programmiersprache gehen.

hustbaer

Bashar schrieb:

mit try ... catch? Dürfte in jeder höheren Programmiersprache gehen.

Nein, ganz sicher nicht.

hustbaer

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.

frosch03

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.

frosch03 schrieb:

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)

naja, normalerweise passiert dem OS nichts, wenn ein prozess sich 'nen stacküberlauf leistet. was eine erkennung oder vermeidung im voraus angeht, könnte man sich sicherlich was ausdenken (wäre vielleicht nicht so ganz kompatibel mit programmiersprachen wie C u.ä.). und dieses 'halteproblem' wird zwar problem genannt, aber 'problem' hört sich schlimmer an als es ist.

rapso

Ishildur schrieb:

Ich erspahre mir also den rekursiven Funktionsaufruf...

du sparst dir vor allem returns.
compiler veruchen das aber schon zu optimieren, wenn du also ne rekursion hast die z.b. immer die selben objekte weitergibt, diese aber nach dem return aus der rekursiven funktion nicht weiter verwendet, werden manche compiler den call+return zu einem simplen jump umstellen.

...Und tausche diesen gegen gleich zwei davon (Push und Pop auf der Hilfstruktur Stack)??

push und pop hast du sowieso auf dem stack, jedoch
-sparst du dir das ablegen von ein paar registern und legst nur wirklich noetige dinge ab
-kannst du cpu freundlicher sein wenn du alle deine variablen per index, also pStack[0]=...;pStack[1]=....; ablegst statt mit *pStack++= zu arbeiten wie es die CPU normalerweise macht.
-..

Ausserdem habe ich dann noch entweder ein new und delete (LinkedList) oder sonstige Umkopiererei (DynamicArray) je nach Stack Implementation.

sowas zu machen waere natuerlich dumm, wenn jemand das vor hat, dann wird er natuerlich schlechter abschneiden als ne rekursion zu machen.
Die idee an sich ist nur die rekursionsaufrufe zu sparen, andere laufzeiteigenschaften sollten sich nicht veraendern. alle allokationen die sonst auf dem stack waeren muessen also weiterhin auf dem stack liegen.

Der Einzige Vorteil für den iterativen Approach sehe ich darin, dass damit die Gefahr eines Überlaufs des Applikationsstacks durch die rekursiven Aufrufe gebannt ist.

nicht sonderlich, man muss beim aufruf der funktion gleich den stack anlegen. man wird also eher merken falls man in einen kritischen bereich kommt (also wenig stack da ist), weil unabhaengig von der rekursionstiefe gleich der volle speicher allokiert ist.
mehr noch, es ist relativ billig nen stackcheck einzubauen, da man das ja nicht rekursiv immer wieder macht, sondern nur im entry der funktion.

Was sagt ihr dazu?

du hast schon recht, die meisten labern bei sowas nach was sie gehoert haben und machen dann implementationsfehler weil sie sich keine gedanken darueber machen "Iterativ ist schneller, basta, aus".

du wirst aber auch vermutlich mal feststellen, dass deine iterative implementierung langsammer ist als die stackversion, obwohl du alles richtig gemacht hast. gruende koennen sein
- dass CPU hersteller (eigentlich nur amd+intel) einiges an optimierungen haben um die ueblichen stackprobleme zu umgehen.
- stack lokalitaet verloren ist aufgrund der initialen grossen allokation, z.b.

uint8_t Stack[1<<20];
size_t StackPtr=0;

sorgt dafuer dass der erste zugriff auf den stackptr garantiert ein cachemiss ist, weil fast alle cpus <=64kb an L1 cache haben, man aber 1MB weiter zugreifen will.
- compiler eben auch stackoptimierungen haben, sie verwenden moeglichst viel wieder an stack memory und versuchen unnoetige rekursionen mit jmps zu ersetzen, was sie nicht machen wenn du per hand in nem loop deinen stack bearbeitest.

am ende hilft nur benchmarken was schneller ist.

hustbaer

frosch03 schrieb:

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?

Dem OS ist das herzlich egal.
Ich denke da gehts eher darum das Programm davor zu schützen dass es seine eigenen Daten überschreibt.

"Neben" dem Stack könnten ja andere Daten liegen. Und ohne Stack-Probes könnte man die überschreiben, ohne jemals die Guard-Page zu treffen. z.B. wenn man von einem grossen Puffer nur einen kleinen Teil verwendet.

Das Programm würde dann ganz normal weiterlaufen, aber der Datenbereich "neben" dem Stack wäre voll mit lauter Schrott aus alten Flippern.

Da ist es denke ich besser, wenn man den Prozess sterben lässt.

BTW: ich weiss garnicht ob man den Prozess sterben lassen *muss* in so einem Fall. Es kann leicht sein, dass man nur den Thread der den Stack-Overflow ausgelöst hat sterben lassen muss. Vielleicht sogar nichtmal den, wobei mir auf die Schnelle aber nicht einfällt, wie man den vernünftig weiterlaufen lassen könnte.

Bashar

hustbaer schrieb:

"Neben" dem Stack könnten ja andere Daten liegen. Und ohne Stack-Probes könnte man die überschreiben, ohne jemals die Guard-Page zu treffen. z.B. wenn man von einem grossen Puffer nur einen kleinen Teil verwendet.

Wozu muss man das überhaupt über eine Guard-Page realisieren? Man kann doch bei jedem Funktionsaufruf erstmal gucken, ob über dem Stackpointer bis zum Beginn des Heaps oder was auch immer danach kommt noch genug Platz ist?

Wenn das ginge, müsste man den Aufruf mit einer Exception sterben lassen und das wärs gewesen. In Java ist das ja leider ein VirtualMachineError, d.h. man kann danach nicht weitermachen, aber dass das zwingend ist, seh ich nicht ganz ein.

Bashar schrieb:

In Java ist das ja leider ein VirtualMachineError, d.h. man kann danach nicht weitermachen, aber dass das zwingend ist, seh ich nicht ganz ein.

kannste aber abfangen, z.b. so:

public class test
{
    static void smash_the_stack()
    {
        smash_the_stack();
    }

    public static void main( String[] args )
    {
        try
        {
            smash_the_stack();    
        }
        catch (StackOverflowError e)
        {
            System.out.println ("huch? ein ... " + e);
        }
        System.out.println ("still alive :)");
    }
}

^^der stack ist danach auch wieder wie neu.

rüdiger

@;fricky
Das ist aber iirc undefined behaviour. Weil es ein VirtualMachineError ist (wie Bashar schon gesagt hat).