Rekursion vermeiden... Wieso?

hustbaer

;fricky schrieb:

hustbaer schrieb:

Man kann die Exception nicht geeignet abfangen, das ist es ja gerade.
...
du kannst in C genauso probleme bekommen, wenn du __finally Blöcke verwendest die einiges an Stack brauchen.

doch, du darfst den stack erst wieder *nach* der exception benutzen, auch nicht in einem __finally-block, weil er dann noch nicht zurückgesetzt wurde. der stackoverflow-verursachende code muss immer in __try/__except eingeschlossen sein, dann wird alles wieder gut. der stackpointer erhält dann wieder den zustand, wie vor dem __try statement. alles was vorher auf dem stack war, behält weiterhin seine gültigkeit.

das ist theoretische und völlig unpraktikable hirnwichserei. interessiert mich kein bisschen. anwendbarkeit = 0.

hustbaer schrieb:

Wenn du C++ programmieren willst kannst du es aber vergessen.

naja, aber C++ kann man auch ohne destruktoren verwenden, wenn sie solche mätzchen machen. das geht bestimmt.

siehe oben. völlig unpraktikabel. kann ich gleich bei C bleiben.
DU magst C++ nicht, gut, bleib bei C. WENN man aber C++ verwendet, dann bitte richtig. und dann kann man keine kunstgriffe brauchen, die es einem verbieten destruktoren zu verwenden.

theoretisch ist viel möglich. bloss sinnvoll ist davon nicht viel.

hustbaer schrieb:

das ist theoretische und völlig unpraktikable hirnwichserei. interessiert mich kein bisschen. anwendbarkeit = 0.

mannomann, natürlich bastelt sich keiner absichtliche stack-overflows oder so, aber das war nie die frage. es gibt seltene situationen, in denen sowas u.ä. vorkommen kann, und dann ist SEH eine sehr willkommene sache.

hustbaer schrieb:

WENN man aber C++ verwendet, dann bitte richtig. und dann kann man keine kunstgriffe brauchen, die es einem verbieten destruktoren zu verwenden.

was richtig oder falsch ist, kann immer noch jeder, situationsbedingt, für sich selbst entscheiden. aber diese starre schwarz/weiss-ganz-oder-garnicht haltung ist ja mal wieder typisch für dich. *cry*

hustbaer

;fricky schrieb:

hustbaer schrieb:

WENN man aber C++ verwendet, dann bitte richtig. und dann kann man keine kunstgriffe brauchen, die es einem verbieten destruktoren zu verwenden.

was richtig oder falsch ist, kann immer noch jeder, situationsbedingt, für sich selbst entscheiden.

es sollte jeder können.
wie man an dir sieht, kann es leider nicht jeder.

volkard

Weiß auch jemand, WARUM der Stackspeicher so beschränkt ist? Normalerweise in C und C++ nur 1MB. Vielleicht sollte man darüber nachdenken, wie man diese beschränkung loswerden kann (oder MMIX kennen).

knivil

Weiß auch jemand, WARUM der Stackspeicher so beschränkt ist?

Ja. Kurz: man braucht fuer gewoehnlich nicht mehr.

Normalerweise in C und C++ nur 1MB.

Beim Compiler fest einstellbar.

Vielleicht sollte man darüber nachdenken, wie man diese beschränkung loswerden kann (oder MMIX kennen).

Oder man nimmt eine Sprache mit virtueller Maschine ohne diese Beschraenkung. Aber dann jammern/mekern alle wieder ueber Performance.

volkard

knivil schrieb:

Weiß auch jemand, WARUM der Stackspeicher so beschränkt ist?

Ja. Kurz: man braucht fuer gewoehnlich nicht mehr.

Eigentlich habe ich die Frage gestallt, damit man drüber nachdenkt.

knivil schrieb:

Normalerweise in C und C++ nur 1MB.

Beim Compiler fest einstellbar.

Und wir beide würden wieder 1M einstellen.

knivil schrieb:

Vielleicht sollte man darüber nachdenken, wie man diese beschränkung loswerden kann (oder MMIX kennen).

Oder man nimmt eine Sprache mit virtueller Maschine ohne diese Beschraenkung. Aber dann jammern/mekern alle wieder ueber Performance.

Sagen wir mal ich hätte 2G RAM. Die Sprache mit VM wird auch abkacken wenn die 2G Ram alle sind.

Warum ist mein Stack auf 1M beschränkt, obwohl ich 2G Speicher zur Verfügung habe? Warum stelle ich das nicht um auf 2G Stackspeicher?

zwutz

volkard schrieb:

Warum ist mein Stack auf 1M beschränkt, obwohl ich 2G Speicher zur Verfügung habe? Warum stelle ich das nicht um auf 2G Stackspeicher?

würde das nicht bedeuten, dass jeder Thread 2GB bekommt? Die werden sich ja kaum einen Stack teilen

volkard

zwutz schrieb:

volkard schrieb:

Warum ist mein Stack auf 1M beschränkt, obwohl ich 2G Speicher zur Verfügung habe? Warum stelle ich das nicht um auf 2G Stackspeicher?

würde das nicht bedeuten, dass jeder Thread 2GB bekommt? Die werden sich ja kaum einen Stack teilen

Ja, das wäre nett. Jeder Prozess hat ja auch 2G Heap.

knivil

Warum ist mein Stack auf 1M beschränkt, obwohl ich 2G Speicher zur Verfügung habe? Warum stelle ich das nicht um auf 2G Stackspeicher?

Also, mal abgesehen vom Unnutzen ist es so, dass ... aber vielleicht sollte ich keine rhetorischen Fragen beantworten ...

volkard schrieb:

Weiß auch jemand, WARUM der Stackspeicher so beschränkt ist? Normalerweise in C und C++ nur 1MB. Vielleicht sollte man darüber nachdenken, wie man diese beschränkung loswerden kann

die 1MB sind ja nur 'ne default-einstellung. unter windoof kannste z.b. 'CreateThread' sagen, wieviel stackspeicher du brauchst. also auch 1000 MB oder 5 bytes, wenn's sein muss.
schau hier: http://msdn.microsoft.com/en-us/library/ms686774(VS.85).aspx

volkard

;fricky schrieb:

volkard schrieb:

Weiß auch jemand, WARUM der Stackspeicher so beschränkt ist? Normalerweise in C und C++ nur 1MB. Vielleicht sollte man darüber nachdenken, wie man diese beschränkung loswerden kann

die 1MB sind ja nur 'ne default-einstellung. unter windows kannste z.b. 'CreateThread' sagen, wieviel stackspeicher du brauchst. also auch 1000 MB oder 5 bytes, wenn's sein muss.
schau hier: http://msdn.microsoft.com/en-us/library/ms686774(VS.85).aspx

Hab ich natürlich alles schon benutzt. Die Frage ist, warum tut man so gerne 1M nehmen statt 2G? Falls jemand meint, daß 2G nicht ginge, warum?

volkard schrieb:

Die Frage ist, warum tut man so gerne 1M nehmen statt 2G? Falls jemand meint, daß 2G nicht ginge, warum?

1MB sind wahrscheinlich ein guter kompromiss. wenn jeder thread schon beim start 2GB virtual memory für nix reservieren würde, wären weniger pages für andere dinge verfügbar.

FlashBurn

Ich habe den Thread nur mal kurz überflogen und wollte mal ein Bsp bringen.

Nehmt den AVL-Baum, den kann man rekursiv und iterativ implementieren. So ich behaupte jetzt das die rekursive Variante ab einer bestimmten Baumgröße weniger Speicher (Stack + Baum) verbraucht als die iterative (Stack + Baum). Denn will man den AVL Baum iterativ implementieren muss man parent Pointer nutzen (da man die "Probleme" ja auf dem Rückweg behebt). Klar ist die iterative schneller (keine ständigen Funktionsaufrufe) und auch ist hier tail-rekursion nicht möglich, da man ja beim zurück springen weiter arbeitet.

So und nun mal dazu was ich unter Rekursion verstehe und was unter Iteration.

Rekursion:

struct node_t *find(struct node_t *node, int val) {
  if(node == 0)
    return 0;

  if(node->val == val)
    return node;

  if(node->val - val > 0)
    return find(node->left,val);
  else
    return find(node->right,val);
}

Und jetzt iterativ:

struct node_t *find(struct node_t *node, int val) {
  while(node) {
    if(node->val == val)
      return node;
    if(node->val - val > 0)
      node= node->left;
    else
      node= node->right;
  }

  return 0;
}

Das wäre auch ein Bsp wo tail-rekursion gehen würde, sollte auch nur ein Bsp sein. Hier wäre die iterative Variante schneller und verbraucht weniger Speicher. Ist halt nur nicht immer so.

volkard

FlashBurn schrieb:

Nehmt den AVL-Baum, den kann man rekursiv und iterativ implementieren. So ich behaupte jetzt das die rekursive Variante ab einer bestimmten Baumgröße weniger Speicher (Stack + Baum) verbraucht als die iterative (Stack + Baum). Denn will man den AVL Baum iterativ implementieren muss man parent Pointer nutzen (da man die "Probleme" ja auf dem Rückweg behebt).

Du vergleichst Äpfel mit Birnen.
Nun ist die maximale Tiefe ja bekannt. Sagen wir mal 40. Nehmen tun Array der Größe 40 und ich kann die History genausogut speichern.

FlashBurn

Wieso ist die maximale Tiefe bekannt?

Wie wäre es denn wenn Jemand mal ein Bsp bringen würde, wo eine Rekursion vermieden werden sollte, zwecks Stackoverflow!?

volkard

FlashBurn schrieb:

Wie wäre es denn wenn Jemand mal ein Bsp bringen würde, wo eine Rekursion vermieden werden sollte, zwecks Stackoverflow!?

Sortiertes Einfügen in eine verkettete Liste.

FlashBurn schrieb:

Wieso ist die maximale Tiefe bekannt?

Weil der Baum ballanciert ist und ein Knoten mindestens zwei Zeiger drin hat Byte hat und nur
a) 64K Speicher adressierbar sind, macht max 16384 Knoten macht maxTiefe < 20
b) 4G Speicher adressierbar sind, macht max 536870912 Knoten macht maxTiefe < 42
c) 16EB Speicher adressierbar sind, macht max 1152921504606846976 Knoten macht maxTiefe < 87

FlashBurn

Das mit der Tiefe ist mir dann auch noch aufgefallen.

Ok, wer kommt aber auf die Idee ein sortiertes Einfügen in eine verkettete Liste rekursiv zu machen? Vorallem, was bringt das?

Ich würde Rekursion nur da anwenden wo es von der Datenstruktur her Sinn macht und eine Liste iteriert man nun mal.

volkard

FlashBurn schrieb:

Ok, wer kommt aber auf die Idee ein sortiertes Einfügen in eine verkettete Liste rekursiv zu machen?

Professoren und Lehrbuchautoren.

FlashBurn schrieb:

Vorallem, was bringt das?

Es bringt mir viel Arbeit, weil ich den N00bs dann wieder ausreden darf, jeden Furz rekursiv zu erzeugen.

FlashBurn

Das ist lustig, alle Professoren die ich bisher hatten, tun sich sogar schwer damit nen Baum rekursiv zu bearbeiten, da ärgern sie lieber die Studenten und machen das ganze iterativ

Also wie gesagt, Rekursion nur da wo es auch Sinn macht (vorallem wenn es den Code vereinfacht), aber iterativ ist eigentlich (weil mir es bestimmt auch Bsp gibt wo es nicht so ist) immer schneller, aber leider oft auch komplexer.

frosch03

Na, das sind jetzt doch sehr persönliche Beweggründe. (Und ich will jetzt garnicht
sagen, dass ich das nicht verstehen und/oder nachvollziehen kann)

Allerdings bin ich der Meinung, dass man einer sehr allgemein gehaltenen
Fragestellung nicht nicht mit so spezielle Antworten entgegentreten sollte.

Listen und Bäume sind nun mal Datenstrukturen, die es auch außerhalb des
imperativen Programmier-Paradigmas gibt. Und daher ist es falsch zu sagen, man
sollte diesen generell nicht mit Rekursion begegnen.

Und um nochmal mit der avl-baum-tiefe zu sticheln :xmas1:
Niemand hat behauptet, dass der Tree die ganze Zeit im RAM liegen muss *duck*

Naja, nichts für ungut ne
frosch03