3. Rekursion vermeiden... Wieso?

Rekursion vermeiden... Wieso?

  • V

    maximAL schrieb:

    Und wie werden rekursive Probleme (wie quicksort) dann gelöst? Eine Stack-Struktur zu benutzen schützt einen ja auch nicht davor, dass der Speicher ausgeht.

    zum beispiel immer zuerst den kleineren ast verfolgen, und den am funktionsende liegenden größeren ast kann man zur schleife umbiegen. damit hats eine rekursionstiefe von max ld(n), auf einem 32-bitter max 32, und dann kann man sich ausdenken, ob man sich 32 leisten mag.

    0
  • R

    maximAL schrieb:

    rüdiger schrieb:

    Ja, ich finde Rekursion auch oft praktisch. Aber ich kann schon verstehen, dass die Embededleute da ein bisschen vorsichtiger sind und MISRA und JSF-Guidelines ua. das verbieten.

    Und wie werden rekursive Probleme (wie quicksort) dann gelöst? Eine Stack-Struktur zu benutzen schützt einen ja auch nicht davor, dass der Speicher ausgeht.

    Wenn malloc/new kein Speicher mehr anfordern können, dann erfährt das das Programm und hat Möglichkeiten darauf entsprechend zu reagieren. Wenn der Stack ausgeht, dann kann man sich davon nicht erholen.

    0
  • V

    Zur Verdeutlichung: quicksort braucht für den rekursiven aufruf zwei zeiger begin/end, eine rücksprungadresse, sind schon 3 zeiger und legen wir noch schäzuingsweise 5 Zeiger dazu. macht 4*8*32=1024 bytes. also ich rechne mit einem stack von 1M und kann mir 1k leisten.
    aber vor allem kann man den bedarf abschätzen und icht nicht so hoffnungslos ausgeliefert. man kann begründen, weshalb man an bestimmten stellen die rekursion für sicher hält.

    0
  • R

    Wenn man auf Rekursion und alloca/VLAs verzichtet, dann kann man den Stackbedarf einfach mit statischer Analyse abschätzen. Daher verstehe ich die Beweggründe.

    Aber bei "normaler Software" dürfte Rekursion den Vorteil haben, dass der Code so leichter zu verstehen ist, als ein auf Iteration umgefrickelter Algorithmus.

    0
  • V

    rüdiger schrieb:

    Aber bei "normaler Software" dürfte Rekursion den Vorteil haben, dass der Code so leichter zu verstehen ist, als ein auf Iteration umgefrickelter Algorithmus.

    und schneller.

    Außerdem ist die statische Analyse einfach zu schlecht unhd inkomplett, wenn man nicht angeben kann, daß eine bestimmte rekursive Funktion sich maximal 32 mal selber aufruft, oder?

    0
  • ?

    Wenn ich euch so zuhöre, frag ich mich, ob es nicht Tools gibt, die die Umwandlung von "rekursiv" zu "iterativ umgefrickelt" automatisch machen. Damit hätte man alle Vorteile.

    0
  • R

    µngbd schrieb:

    Wenn ich euch so zuhöre, frag ich mich, ob es nicht Tools gibt, die die Umwandlung von "rekursiv" zu "iterativ umgefrickelt" automatisch machen. Damit hätte man alle Vorteile.

    Bei Tailrekursion können einige Compiler (zB der GCC ist da wohl recht gut) das auch automatisch. Aber bei komplizierteren Sachen, wird es recht schwierig, da dies massive Codeänderungen erfordern würde.

    volkard schrieb:

    Außerdem ist die statische Analyse einfach zu schlecht unhd inkomplett, wenn man nicht angeben kann, daß eine bestimmte rekursive Funktion sich maximal 32 mal selber aufruft, oder?

    Ja, leider sind die meisten Entwicklungstools für C bzw. C++ sehr primitiv.

    0
  • I

    @hustbaer

    BTW: wer versucht Rekursion durch einen Stack zu ersetzen, und dann der Einfachkeit halber einen std::vector<> als Stack verwendet, der wird sein blaues Wunder erleben.

    Genau dieser Punkt interessiert mich nun:
    Bist du dir ganz sicher, dass ein std::vector soviel langsamer als eine std::list ist? Die erforderliche Kapazität ist ja beim Beginn des Traversals bekannt. Das interne Array muss also nicht mehr wachsen...

    Nehmen wir einen kompletten Binärbaum der Tiefe 16.

    Stack implementiert als Dynamische Array mit einer dynamischen Startkapazität von Baumtiefe-1:
    -------------------------------------------------------------------------
    1*(new+delete), fertig, temporärer Speicheroverhead während Traversal: 60Bytes bei 32-Bit System, 120Bytes bei 64-Bit System.

    Stack implementiert als Verkettete Liste:
    ----------------------------------------
    32'768*(new+delete),temporärer Speicheroverhead während Traversal: 60Bytes bei 32-Bit System, 120Bytes bei 64-Bit System.

    Meine Berechnungen gehen davon aus, dass der unterste Level niemals auf dem Stack liegt.

    Gruss Samuel

    0

  • Ishildur schrieb:

    @hustbaer

    BTW: wer versucht Rekursion durch einen Stack zu ersetzen, und dann der Einfachkeit halber einen std::vector<> als Stack verwendet, der wird sein blaues Wunder erleben.

    Genau dieser Punkt interessiert mich nun:
    Bist du dir ganz sicher, dass ein std::vector soviel langsamer als eine std::list ist? Die erforderliche Kapazität ist ja beim Beginn des Traversals bekannt. Das interne Array muss also nicht mehr wachsen...

    Wo liest du da was vonwegen std::list raus? Ich meinte std::vector im Gegensatz zu einem Array auf dem Stack.

    std::vector wird deswegen langsamer sein als eine rekursive Variante, weil std::vector "new" aufruft, und die rekursive Variante das "einsparen" kann. Und "new" ist teuer. Und genauso ist std::vector langsamer als ein Array auf dem Stack.

    0
  • I

    Sorry, hab noch die Berechnungen verändert, während du am schreiben warst.
    Jtzt stimmts hoffentlich 🙄

    Sorry, war eine reine Mutmassung, hast du natürlich nicht gesagt 😉
    Aber das native c-array muss ich doch auch zur Laufzeit allozieren, genauso wie den Vector? Da sollte es doch keinen Unterschied machen?

    0

  • Achja...

    Nehmen wir einen kompletten Binärbaum der Tiefe 16.

    Stack implementiert als Dynamische Array mit einer dynamischen Startkapazität von 2^Baumtiefe = 65536:

    Was willst du denn machen, wo du für jeden Knoten einen Eintrack am Stack bräuchtest? Für einen 16 Ebenen tiefen Baum hast du üblicherweise eine Rekursions-Tiefe von <= 16. Gerade deswegen ist es ja auch kein Problem rekursive Algorithmen zu verwenden.

    0
  • I

    @hustbear
    Ja da hast du völlig recht, hab nicht gerade viel überlegt als ich den Eintrag geschrieben hatte und erst nach und nach diese Erkenntniss, als ich nach dem Schreiben weiter über dieses Problem nachdachte 😃

    0
  • K

    µngbd schrieb:

    Wenn ich euch so zuhöre, frag ich mich, ob es nicht Tools gibt, die die Umwandlung von "rekursiv" zu "iterativ umgefrickelt" automatisch machen. Damit hätte man alle Vorteile.

    Das ist im Allgemeinen nicht moeglich.

    0
  • I

    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 😋

    0
  • J

    knivil schrieb:

    µngbd schrieb:

    Wenn ich euch so zuhöre, frag ich mich, ob es nicht Tools gibt, die die Umwandlung von "rekursiv" zu "iterativ umgefrickelt" automatisch machen. Damit hätte man alle Vorteile.

    Das ist im Allgemeinen nicht moeglich.

    Warum? Ich hab mal irgendwann gelernt, dass rekursive Berechenbarkeit und while-Berechenbarkeit dasselbe sind, man also jedes Programm als while-Programm und sogar mit nur einer Schleife schreiben kann. Oder spielst Du eher auf Probleme bei der automatischen Umsetzung an? Wenn ja, wo hakt es da genau?

    0
  • K

    rekursive Berechenbarkeit und while-Berechenbarkeit dasselbe sind

    Weil man einen Stack simulieren kann. Aber dann hat man immer noch einen rekursiven Algorithmus. Gewonnen hat man damit aber noch nichts.

    0
  • N

    Ishildur schrieb:

    Aber das native c-array muss ich doch auch zur Laufzeit allozieren, genauso wie den Vector? Da sollte es doch keinen Unterschied machen?

    Nein, wenn du das Array auf den Stack legst, reicht eine Stackpointer-Verschiebung, das ist sehr effizient. Bei new muss hingegen zuerst ein freier Speicherbereich auf dem Freestore gesucht und beschafft werden. Dafür hat man damit mehr Flexibilität.

    0
  • J

    knivil schrieb:

    rekursive Berechenbarkeit und while-Berechenbarkeit dasselbe sind

    Weil man einen Stack simulieren kann. Aber dann hat man immer noch einen rekursiven Algorithmus. Gewonnen hat man damit aber noch nichts.

    Okay, dann haben wir ein Definitionsproblem. Für mich war Rekursion bis jetzt grundsätzlich damit verbunden, dass eine Funktion sich selbst (möglicherweise über Umwege) aufruft. Jetzt sagst Du, dass der Algorithmus auch dann rekursiv bleibt, wenn sich nichts selber aufruft. Woran machst Du fest wann ein Algorithmus rekursiv ist und wann nicht?

    0
  • I

    @Nexus
    Ja schon, aber dann haben wir das Problem, dass eine gewisse Tiefe des entsprechenden Baumes nicht überschritten werden darf...

    0
  • K

    Die Fakultaet wird gern dafuer herangezogen. Dazu mal etwas Code, z.B. in Haskell:

    fac' 0 = 1
fac' n = n * fac' (n-1)

    Dabei wird die erste Funktion so ausgewertet:

    fac' 3
3 * fac' 2
3 * 2 * fac' 1
3 * 2 * 1 * fac' 0
3 * 2 * 1 * 1
3 * 2 * 1
3 * 2
6

    Dabei faellt auf, dass der Speicher fuer Zwischenergebnisse waechst (im Verhaeltnis zur Ein- bzw. Ausgabe). Das kann ich natuerlich auch mit while und einem kuenstlichen Stack simulieren. Iterativ ist es damit noch lange nicht, auch wenn while gerne damit assoziiert wird.

    fac'' n = helper n 1
    where helper 0 acc = acc
          helper n acc = helper (n-1) (n*acc)

    Hier wird helper auch rekursiv aufgerufen, aber insgesamt ist es ein iterativer Prozess. Die Funktion wird wie folgt ausgewertet:

    fac'' 3
helper 3 1
helper 2 3
helper 1 6
helper 0 6
6

    Dabei waechst der Speicher nicht, sondern ist beschraenkt.

    0
Anmelden zum Antworten